Craig Rodrigues!

Jun 8 Learning to Code: Week 4 - Algorithms

6/1/16 - Continued

• Sara recommended Codecademy. They don’t have a C class, but they do have Python, HTML, CSS etc. Also they have one on learning the Command Line and learning Git.
• I have decided what meetup to attend (goal deadline today): June 25th http://www.meetup.com/CodeNewbie-Atlanta/events/229361891/

6/2/16

• Shawn helped me look into making a function for the water.c program. I worked on it for a bit.
• Error 1 - 0 arguments instead of 2. • Error 2 - variable bottles but nothing there. Call the function INTO that variable? • Boom, got it to work. That was pretty cool.
• Now I can account for variable shower heads.
• I think the input question could be better to explain what the metric is for waterflow etc.
• I didn’t think of rounding errors.
#include <stdio.h>
#include <cs50.h>

// function that returns the number of 16oz bottles used
int getBottles(int time, int showerflow)
{
return (time * showerflow)/16;
}

int main(void)
{
printf("How long did you shower today? (minutes)\n");
int time = GetInt();

int showerflow = GetInt();

int bottles = getBottles(time, showerflow);
printf("Minutes Showered: %i\n16oz Bottles Used: %i\n", time, bottles);
}

I put a function in Caesar.c!

#include <stdio.h>
#include <cs50.h>
#include <string.h>
#include <ctype.h>

/**
* Caesar.c
* A program that encrypts messages using Caesar’s cipher. Your program must
* accept a single command-line argument: a non-negative integer. Let’s call it
* k for the sake of discussion. If your program is executed without any
* command-line arguments or with more than one command-line argument, your
* program should yell at the user and return a value of 1.
*
* */

// function that encrypts a character based on the key submitted
int encryptCode(char code, int key)
{
if islower(code)
{
code = ((((code + key) - 97) % 26) + 97);
return code;
}
else if isupper(code)
{
code = ((((code + key) - 65) % 26) + 65);
return code;
}

//if neither then just return whatever it is
else
return code;
}

int main(int argc, string argv[])
{
// check for 2 arguments only
if (argc != 2)
{
printf("Nope\n");
return 1;
}

// once I check for correct argv put key into an int k
int k = atoi(argv);

// check if the integer is non-negative
if (k < 0)
{
printf("Nope\n");
return 1;
}
else
{
// prompt user for a code to encrypt
string code = GetString();

for (int i = 0, n = strlen(code); i < n; i++)
{
printf("%c", encryptCode(code[i], k););
}
printf("\n");
return 0;
}
}
• Not sure about the names of the variables though. I think it works okay.
• Also not sure if functions should be in printf or on a separate line going into another variable?
• Example: printf("%c", encryptCode(code[i], k));
printf("%c", encryptCode(code[i], k));

6/3/16

• Got stuck in a few places on Credit but eventually solved it after working on it for an hour this morning. I need to extract a few functions to make the program really the way I want it, but right now it functionally is correct!
• That one was tough. I decided to use arrays, but I’m not sure if that is ideal. I feel like there are easier ways to manipulate digits of a number without putting each digit into a slot in an array.
• So far I am using a massive number of printf statements inside my program to be able to check if things are working. Don’t know of a better way at the moment.
• See below for what I did. • SOLUTION HERE (haven’t extracted all functions I wanted to):
#include <stdio.h>
#include <cs50.h>
#include <string.h>
#include <ctype.h>
#include <math.h>

// calculates the number of digits in the card number
int getCardDigits(long long card_num)
{
int card_digits = (int)log10(card_num) + 1;
return card_digits;
}

int main(void)
{
// get card number from user
printf("Number: ");
long long card_num = GetLongLong();

// use digits function
int card_digits = getCardDigits(card_num);

// if not a valid credit card length print invalid immediately
if (card_digits != 13 && card_digits != 15 && card_digits != 16)
{
printf("INVALID\n");
return 0;
}

// storing the individual digits in an array
int numberArray[card_digits];
long long count = card_num;
int i = 0;

while (count != 0)
{
numberArray[card_digits - 1 - i] = count % 10;
count = count/10;
i++;
}

// Every other number starting from the second to last in array
int numberArray2[card_digits/2];
int k = 2;
int l = 0;

while ((card_digits - k) > -1)
{
numberArray2[l] = 2 * numberArray[card_digits - k];
k = k + 2;
l++;
}

int digit_times_two = 0;

for (int j = 0; j < card_digits/2; j++)
{
if (numberArray2[j] > 9)
{
int split_digit = 0;
digit_times_two = digit_times_two + (numberArray2[j] % 10);
split_digit = numberArray2[j]/10;
digit_times_two = digit_times_two + split_digit;
}
else
{
digit_times_two = digit_times_two + numberArray2[j];
}
}

// the remainging digits added together after put in 3rd array
int numberArray3[card_digits - (card_digits/2)];
int m = 1;
int n = 0;

while ((card_digits - m) > -1)
{
numberArray3[n] = numberArray[card_digits - m];
m = m + 2;
n++;
}

int other_digit_count = 0;

for (int j = 0; j < (card_digits - (card_digits/2)); j++)
{
other_digit_count = other_digit_count + numberArray3[j];
}

int companyId;
int companyId2;

// validating Luhn algorithm
if ((digit_times_two + other_digit_count) % 10 == 0)
{
companyId = numberArray;
companyId2 = numberArray;
}
else
{
printf("INVALID\n");
return 0;
}

// checking which card company
if (card_digits == 15 && companyId == 3 && (companyId2 == 4 || companyId2 == 7))
{
printf("AMEX\n");
}
else if (card_digits == 16 && companyId == 5 && (companyId2 >= 1 && companyId2 <= 5))
{
printf("MASTERCARD\n");
}
else if ((card_digits == 13 || card_digits == 16) && companyId == 4)
{
printf("VISA\n");
}
else
{
printf("INVALID\n");
}

return 0;
}

STEPS:

1. Prompt user for credit card number. (long long)
2. Check length of the card #. If not valid print INVALID.
3. Function: cardLength to get the number of digits in a card number using Log10 + 1.
4. Put the digits into an array by using % and a loop and /10 etc.
5. Loop from the back to the front of the new array of digits and take every other digit.
6. Multiply the results of 5 by 2.
7. Add the individual digits together (what do you do about double digits?)
8. Add to #7 the sum of the remaining digits.
9. If answer to #8's final digit is a zero then the card number is legit.
10. Check the card's first digit(s) to get the card company.
11. If #9 & #10 are true then print out what card company it is and return 0.

NOTES/THOUGHTS:

• Had to do a bit of research for the questions I had such as how to find out the number of digits in an integer and how to put the individual digits of a number into an array. Once I found those it was just a matter of piecing the puzzle together doing down the list of steps above.
• One loop I had initialized the counter i inside the loop itself so it actually never incremented. That took a while to see, yet it was such a simple problem!
• I had to figure out how to reverse a loop to put the digits into it back to front instead of front to back.
• Put "return 1" in a couple of places when the program really wanted "return 0" regardless.
• Need to remember that using the data type int only takes the integer portion not anything after the decimal. Useful to remember for this problem set.
• Bought the Grokking Algorithms book as next lecture begins to talk about them and big O notation.

Nothing today 😢

6/5/16

Week 3 - Lecture 1

• Bubble sort: Taking two things and comparing them then moving through the array. If not sorted after that doing it again. Pretty damn slow.
• Selection sort: going through the list and selecting the next smallest element and moving it to the front.
• Insertion sort: Go through the list and insert the smallest number where it should be, pushing everything else forward. Don’t have to go back through the list more than once.
• Big O describes the upper bound on an algorithm. Bubble Sort, selection and insertion sort big O is n2.
• Big O = worst case scenario.
• Binary Search has a Big O of n.
• Binary search: Divide and conquer (phone book example) is O = log n since the list gets half as small every time.
• Ω (omega) is the lower bound on an algorithm. Best case scenario.
• Video: What Different Sorting Algorithms Sound Like
• Video: Why Study Algorithms?

Week 3 - Lecture 2 6/6/16

Very cool blog posts from someone who successfully followed the path I want to (also very intimidating):

If you’re struggling to understand a concept in a book or on Wikipedia, look up Youtube videos of people explaining it in different ways until you get it. I’ve found this strategy amazingly effective.

SECTION VIDEOS & SHORTS

• GDB
• Computational Complexity
• Selection Sort
• Insertion Sort
• Merge Sort
• Linear Search
• Binary Search
• Algorithms Summary
• Asymptotic Notation
• Quicksort

6/7/16

• Worked on pset 3 Game of Fifteen.
• Binary Search Trees
• Another video on debugging with GDB (23 min). Incredibly useful video.
• An unsigned int is just an int that cannot be negative.
• Finished generate.c by adding comments to distribution code.
• https://reference.cs50.net/stdlib.h/drand48 was a useful resource.

6/8/16

/**
* helpers.c
*
* Computer Science 50
* Problem Set 3
*
* Helper functions for Problem Set 3.
*/

#include <cs50.h>

#include "helpers.h"

/**
* Returns true if value is in array of n values, else false.
*
* Re-write search in such a way that it uses linear search,
* returning true if value is in values and false if value is not in values.
* Take care to return false right away if n isn’t even positive.
*/
bool search(int value, int values[], int n)
{
// linear search algorithm
for (int i = 0; i < n; i++)
{
if (values[i] == value)
return true;
}

return false;
}

/**
* Sorts array of n values.
*/
void sort(int values[], int n)
{
// TODO: implement an O(n^2) sorting algorithm
return;
}
• Worked on implementing Insertion sort - pseudocode from wikipedia really helped me visualize how to get it to work. /**
* helpers.c
*
* Computer Science 50
* Problem Set 3
*
* Helper functions for Problem Set 3.
*/

#include <cs50.h>

#include "helpers.h"

/**
* Returns true if value is in array of n values, else false.
*
* Re-write search in such a way that it uses linear search,
* returning true if value is in values and false if value is not in values.
* Take care to return false right away if n isn’t even positive.
*
* Implement sort so that the function actually sorts, from smallest to largest,
* the array of numbers that it’s passed, in such a way that its running time is
* in O(n2), where n is the array’s size.
*/

// linear search algorithm
// bool search(int value, int values[], int n)
// {
//    for (int i = 0; i < n; i++)
//    {
//        if (values[i] == value)
//            return true;
//    }
//
//    return false;
// }

bool binarySearch(int value, int values[], int min, int max)
{
int midpoint = 0;

if (max < min)
return false;
else
midpoint = (max + min)/2;

if (values[midpoint] < value)
return binarySearch(value, values, midpoint + 1, max);
else if (values[midpoint] > value)
return binarySearch(value, values, min, midpoint - 1);
else if (value == values[midpoint])
return true;
else
return false;
}

// binary search algorithm
bool search(int value, int values[], int n)
{
return binarySearch(value, values, 0, n-1);
}

/**
* Sorts array of n values.
*
*  Holds current value in a temporary block and compares that to the left of
*  it in the array. If j-1 is less than the temp then move j-1 to one to the right.
*  Do that until you find a value that is less than the temp. Insert temp right
*  where you stopped.
*
*/
void sort(int values[], int n)
{
// insertion sort algorithm

for (int i = 1; i < n; i++)
{

int temp = values[i];
int j = i;

while (j > 0 && (values[j-1] > temp))
{
values[j] = values[j-1];
j--;
}
values[j] = temp;
}
return;
}

If you somehow stumbled upon my blog and read this far and have questions just hit me up on Twitter or just email me!