Skip to content

Latest commit

 

History

History
273 lines (218 loc) · 10.1 KB

README.md

File metadata and controls

273 lines (218 loc) · 10.1 KB

Week 3

Lab: Sort

Analyze three sorting programs to determine which algorithms they use.

Provided to you are three already-compiled C programs, sort1, sort2, and sort3. Each of these programs implements a different sorting algorithm: selection sort, bubble sort, or merge sort (though not necessarily in that order!). Your task is to determine which sorting algorithm is used by each file.

  • sort1, sort2, and sort3 are binary files, so you won’t be able to view the C source code for each. To assess which sort implements which algorithm, run the sorts on different lists of values.
  • Multiple .txt files are provided to you. These files contain n lines of values, either reversed, shuffled, or sorted.
    • For example, reversed10000.txt contains 10000 lines of numbers that are reversed from 10000, while random10000.txt contains 10000 lines of numbers that are in random order.
  • To run the sorts on the text files, in the terminal, run ./[program_name] [text_file.txt]. Make sure you have made use of cd to move into the sort directory!
    • For example, to sort reversed10000.txt with sort1, run ./sort1 reversed10000.txt.
  • You may find it helpful to time your sorts. To do so, run time ./[sort_file] [text_file.txt].
    • For example, you could run time ./sort1 reversed10000.txt to run sort1 on 10,000 reversed numbers. At the end of your terminal’s output, you can look at the real time to see how much time actually elapsed while running the program.
  • Record your answers in answers.txt, along with an explanation for each program, by filling in the blanks marked TODO.

Problem Set

Plurality

For this program, you’ll implement a program that runs a plurality election, per the below.

$ ./plurality Alice Bob Charlie
Number of voters: 4
Vote: Alice
Vote: Bob
Vote: Charlie
Vote: Alice
Alice

Complete the implementation of plurality.c in such a way that the program simulates a plurality vote election.

  • Complete the vote function.
    • vote takes a single argument, a string called name, representing the name of the candidate who was voted for.
    • If name matches one of the names of the candidates in the election, then update that candidate’s vote total to account for the new vote. The vote function in this case should return true to indicate a successful ballot.
    • If name does not match the name of any of the candidates in the election, no vote totals should change, and the vote function should return false to indicate an invalid ballot.
    • You may assume that no two candidates will have the same name.
  • Complete the print_winner function.
    • The function should print out the name of the candidate who received the most votes in the election, and then print a newline.
    • It is possible that the election could end in a tie if multiple candidates each have the maximum number of votes. In that case, you should output the names of each of the winning candidates, each on a separate line.

You should not modify anything else in plurality.c other than the implementations of the vote and print_winner functions (and the inclusion of additional header files, if you’d like).

Your program should behave per the examples below.

$ ./plurality Alice Bob
Number of voters: 3
Vote: Alice
Vote: Bob
Vote: Alice
Alice

$ ./plurality Alice Bob
Number of voters: 3
Vote: Alice
Vote: Charlie
Invalid vote.
Vote: Alice
Alice

$ ./plurality Alice Bob Charlie
Number of voters: 5
Vote: Alice
Vote: Charlie
Vote: Bob
Vote: Bob
Vote: Alice
Alice
Bob

Tideman

Complete the implementation of tideman.c in such a way that it simulates a Tideman election.

  • Complete the vote function.
    • The function takes arguments rank, name, and ranks. If name is a match for the name of a valid candidate, then you should update the ranks array to indicate that the voter has the candidate as their rank preference (where 0 is the first preference, 1 is the second preference, etc.)
    • Recall that ranks[i] here represents the user’s ith preference.
    • The function should return true if the rank was successfully recorded, and false otherwise (if, for instance, name is not the name of one of the candidates).
    • You may assume that no two candidates will have the same name.
  • Complete the record_preferences function.
    • The function is called once for each voter, and takes as argument the ranks array, (recall that ranks[i] is the voter’s ith preference, where ranks[0] is the first preference).
    • The function should update the global preferences array to add the current voter’s preferences. Recall that preferences[i][j] should represent the number of voters who prefer candidate i over candidate j.
    • You may assume that every voter will rank each of the candidates.
  • Complete the add_pairs function.
    • The function should add all pairs of candidates where one candidate is preferred to the pairs array. A pair of candidates who are tied (one is not preferred over the other) should not be added to the array.
    • The function should update the global variable pair_count to be the number of pairs of candidates. (The pairs should thus all be stored between pairs[0] and pairs[pair_count - 1], inclusive).
  • Complete the sort_pairs function.
    • The function should sort the pairs array in decreasing order of strength of victory, where strength of victory is defined to be the number of voters who prefer the preferred candidate. If multiple pairs have the same strength of victory, you may assume that the order does not matter.
  • Complete the lock_pairs function.
    • The function should create the locked graph, adding all edges in decreasing order of victory strength so long as the edge would not create a cycle.
  • Complete the print_winner function.
    • The function should print out the name of the candidate who is the source of the graph. You may assume there will not be more than one source.

You should not modify anything else in tideman.c other than the implementations of the vote, record_preferences, add_pairs, sort_pairs, lock_pairs, and print_winner functions (and the inclusion of additional header files, if you’d like). You are permitted to add additional functions to tideman.c, so long as you do not change the declarations of any of the existing functions.

Your program should behave per the example below:

./tideman Alice Bob Charlie
Number of voters: 5
Rank 1: Alice
Rank 2: Charlie
Rank 3: Bob

Rank 1: Alice
Rank 2: Charlie
Rank 3: Bob

Rank 1: Bob
Rank 2: Charlie
Rank 3: Alice

Rank 1: Bob
Rank 2: Charlie
Rank 3: Alice

Rank 1: Charlie
Rank 2: Alice
Rank 3: Bob

Charlie

Practice Problems

Recursive atoi

Learning Goals

  • Deepen an understanding of strings
  • Practice creating recursive functions

In the recursive version of convert, start with the last char and convert it into an integer value. Then shorten the string, removing the last char, and then recursively call convert using the shortened string as input, where the next char will be processed.

Your program should behave per the examples below.

atoi/ $ ./atoi
Enter a positive integer: 3432
3432

atoi/ $ ./atoi
Enter a positive integer: 98765
98765

Average Temperatures

Learning Goals

  • Practice working with structs
  • Practice applying sorting algorithms

The main function initializes the temps array, calls the sort_cities function and prints out the array in sorted order. You will use an O(n2) sorting algorithm of your choice (possibly bubble sort, selection sort, or insertion sort) to sort the array by temperature, in descending order.

Your program should behave per the examples below.

temps/ $ ./temps

Average July Temperatures by City

Phoenix: 107
Las Vegas: 105
Austin: 97
Miami: 97
Denver: 90
Chicago: 85
New York: 85
Boston: 82
Los Angeles: 82
San Francisco: 66
temps/ $

Max

Learning Goals

  • Pass an array into a function
  • Create a helper function that finds a maximum value

The main function initializes the array, asks the user to enter values, and then passes the array and the number of items to the max function. Complete the max function by iterating through every element in the array, and return the maximum value.

Your program should behave per the examples below.

max/ $ ./max
Number of elements: 3
Element 0: 2
Element 1: 10
Element 2: -1
The max value is 10.

max/ $ ./max
Number of elements: 4
Element 0: -100
Element 1: -200
Element 2: -3
Element 3: -5000
The max value is -3.

Snackbar

Learning Goals

  • Practice using structs
  • Write a linear search algorithm

The main function is already complete. After calling add_items to initialize the menu array, it will print out the menu items and their prices, prompting you to keep selecting items until you press enter without typing anything in. You are to complete two functions, add_items, which adds at least the first four menu items, and get_cost to return the cost of each item. When you are creating a linear search algorithm in get_cost, do make sure that it is case insentive.

Your program should behave as follows:

snackbar/ $ ./snackbar

Welcome to Beach Burger Shack!
Choose from the following menu to order. Press enter when done.

Burger: $9.50
Vegan Burger: $11.00
Hot Dog: $5.00
Cheese Dog: $7.00
Fries: $5.00
Cheese Fries: $6.00
Cold Pressed Juice: $7.00
Cold Brew: $3.00
Water: $2.00
Soda: $2.00

Enter a food item: burger
Enter a food item: fries
Enter a food item: soda
Enter a food item: 

Your total cost is: $16.50

snackbar/ $ ./snackbar

Welcome to Beach Burger Shack!
Choose from the following menu to order. Press enter when done.

Burger: $9.50
Vegan Burger: $11.00
Hot Dog: $5.00
Cheese Dog: $7.00
Fries: $5.00
Cheese Fries: $6.00
Cold Pressed Juice: $7.00
Cold Brew: $3.00
Water: $2.00
Soda: $2.00

Enter a food item: cold brew
Enter a food item: hot dog
Enter a food item: 

Your total cost is: $8.00

Note that the menu should only print out the items that you saved in the menu array.