If you get stuck, you may also wish to check out the hints, although not many are included.


assignment goals

  • Learn about the design, analysis, and implementation of algorithms.

  • No new C concepts, but you are starting with a completely blank screen. The training wheels are off!

    • grading breakdown
    Here is the approximate grading breakdown. Note the relatively high number of points for your answers to the questions in the readme file.

  • brute.c (3 points)

  • better.c (1 point)

  • conquer.c (3 points)

  • readme (3 points)

    • sample inputs and reference solutions

  • You may wish to test your code on various test inputs that are located at /u/cs126/files/pit/. Since some of the data files are rather large, you may not want to copy them into your arizona account. Instead, you can access them directly with the following syntax: 
    phoenix.Princeton.EDU% a.out < /u/cs126/files/pit/pit1000.txt
  • We won't post reference solutions; instead you can use the command 
    phoenix.Princeton.EDU% /u/cs126/bin/pit < /u/cs126/files/pit/pit1000.txt
    to check your answers with our reference algorithm. Don't worry if your algorithms are not quite as fast as our professionally crafted one! (Feel free to challenge yourself and attempt to match or beat our algorithm.)

  • You may assume the input file contains at most 2 million integers. Each integer is between -1,000 and 1,000, but don't worry if your algorithm doesn't use this information.

  • Note: we've just added some really huge data files (5-10 million elements) for your enjoyment. However, to read in arrays this large on arizona, you must either define the array to be a global variable or allocate it dynamically using malloc.

    • measuring performance empirically

  • Use the Unix command /usr/bin/time to measure the execution time of a program, as in the TSP assignment. 
    phoenix.Princeton.EDU% /usr/bin/time a.out < pit100.txt
  • Count the number of times each instruction is executed using the lcc compiler, as in Lecture T5. 
    phoenix.Princeton.EDU% rm prof.out
phoenix.Princeton.EDU% lcc -b brute.c
phoenix.Princeton.EDU% a.out < pit100.txt
phoenix.Princeton.EDU% bprint
    Don't forget to delete the old prof.out file each time - it doesn't seem to get done automatically.

    • measuring performance analytically

  • We have created some new analysis of algorithms exercises that are meant to give you some practice and experience with big Oh notation.

  • It is inappropriate to ask the lab TA's for help on big Oh notation or other questions specific to the assignment. You should only ask them general C or Unix related questions. See your preceptor for questions like this.

    • submission and readme
  • Use the following submit command: 
    phoenix.Princeton.EDU% /u/cs126/bin/submit 8 readme brute.c better.c conquer.c

  • Here is a readme template to assist you. It should contain:

  • Name, precept number, high level description of code, any problems encountered, and whatever help (if any) your received.

  • Also, answer the following questions for each of your three algorithms:

  • Give the theoretical complexity (use big Oh notation) of each of your algorithms. Justify your answer.

  • Do your empirical observations (results of /usr/bin/time and bprint) agree with your theoretical estimates?

  • What is the largest problem you can solve in 1 minute?

  • Now, estimate the largest problem that you can solve in 1 week (roughly 10,000 minutes).

    • Enrichment Links

  • Here's an open-pit mining applet that solves a two-dimensional version of the problem.


    • Kevin Wayne