Chunk 3.1: Computational Complexity

  • Watch the lecture from 0:00 - 26:14. We will cover this material in class as well, so you can skip this portion unless you miss class or need reinforcement of the concepts. In-class slides can be found here.

Questions

  • Answer these questions (submit on Classroom):
    1. Describe Big O notation. What quality of an algorithm does it describe?
    2. Define an algorithm in English for linear search.
    3. Define an algorithm in English for binary search.
    4. Describe Big Ω notation. What quality of an algorithm does it describe?

Problem: Largest

  • Implement a program in C in a file named largest.c which accepts any number of random integers as arguments and prints the highest number in the list. The inputs should be separated by spaces (this is what makes them separate arguments) and the program should return a usage error if there are no arguments. You don’t have to handle any other errors and can assume that all arguments are positive or negative integers.
    • Execute wget https://cs-acs.com/assets/source_code/largest.c to download this problem’s distribution code.
$ ./largest
Usage: ./largest [int 1] [int 2] ...

$ ./largest 1
1

$ ./largest -5 10 30 1 5 9 8
30

Check & Submit

Check style with style50:

style50 largest.c

Check functionality with check50:

check50 cs-acs/problems/main/largest

Submit with submit50:

submit50 cs-acs/problems/main/largest