CSC300: Homework (Order of Growth, Sorting Problems)

(Click here for one slide per page)

• Re-read the section on Binary Search in Algorithms, pages 378-386.

• Review Section 1.4 (Analysis of Algorithms) in the Algorithms textbook.

• Read pages 244 - 257 of Section 2.1 (Elementary Comparison-Based Sorting) in the Algorithms textbook.

• Do Quiz 4 on D2L. Note: There is no Quiz 3, because I number the quizzes based on the week they were assigned.

• Section 810 Async: Print out and do the In Class Coding Activity, which is a mini-practice exam.

  In-Class Coding Activity Pop Quiz (PDF file)

  You should be able to do this activity in 10 minutes or less.

  I can't control whether you do it under exam conditions, but you should try to do it without reference to any external resources, just as you will have to take the Midterm.

  Submit it in the appropriate folder labeled In-Class Coding Activity on D2L. Submission of this activity counts toward your participation grade for Week 4.

  If you are in Section 801, and were not present at the beginning of class, you should do this activity as described above and submit it as well.

• Do the homework assigned on D2L (See Submissions).

  There are two parts to this homework. Do the hw4a, the programming homework, before the hw4b written homework, as the programming part should help you better understand the material in hw4b.

  • hw4a: Order of Growth Experiments

    file:orderofgrowth.zip (Zip file)

    Once you have downloaded the file, unzip it. The orderofgrowth folder inside of it should be added below the ds1.student package in IntelliJ IDEA. Make sure you can compile all of the code in IntelliJ IDEA (no red squiggly marks).

    There are a lot of files in this zip. Two of them, CountingLoops.java and CountingLoopsRecursion.java are demos from class, which may be useful to you, but they are not necessary for this part of the homework.

    There are a few other support files, which you can look at if you want to, but don't change any file not listed below. Within the files listed below, make sure you don't change anything I specifically instructed you not to in the comments.

    The Java classes with instructions in the source files are as follows. Go through them in this order. Each of these have main programs. Look for the TODO comments (as usual).

    Do not use recursion for any of the coding questions. Use loops.

    1. ds1.student.orderofgrowth.max.SlowerMax

       This is an example experiment with a slow implementation of finding the max. Look for TODOs and instructions to provide answers to the questions included in the file.

    2. ds1.student.orderofgrowth.max.FasterMax

       This is an example experiment with a more efficient implementation of finding the max. Look for TODOs and instructions to provide answers to the questions included in the file.

    3. ds1.student.orderofgrowth.search.LinearSearch

       This is an example experiment with an inefficient search for a value in an array. Look for TODOs and instructions to provide answers to the questions included in the file.

    4. ds1.student.orderofgrowth.search.BinarySearch

       For this Java class, you will need to actually implement binary search, write unit tests, and run some experiments. Look for TODOs and instructions to provide answers to the questions included in the file.

    5. ds1.student.orderofgrowth.sort.DoubleArraySelectionSort

       For this Java class, you will need to actually implement selection sort, write unit tests, and run some experiments. Look for TODOs and instructions to provide answers to the questions included in the file.

    6. ds1.student.orderofgrowth.sort.DoubleArrayInsertionSort

       For this class, you will need to actually implement insertion sort, write unit tests, and run some experiments. Look for TODOs and instructions to provide answers to the questions included in the file.

    Hand in all six of the above listed files in the hw4a folder.

    Your submissions should contain your implementations of the requested algorithms, any unit tests requested, and answers to the questions about interpreting the results in the designated comment blocks.

    Important Study Note

    My reason for asking you to code these algorithms yourself is because I want you to get the practice thinking through a problem and trying it out yourself. You don't even need to code the algorithms exactly as presented in the textbook. Just remember that you need to know these algorithms cold so that if I ask you to implement them on an exam, you know how to do it without consulting any external resources.

• hw4b: Sorting Problems

  Do these problems from Algorithms on paper, and hand them in (Word doc or PDF). The problems are begin page 264 of the Algorithms text.

      2.1.1
      2.1.2
      2.1.4
      2.1.6
      2.1.7
      2.1.8
      2.1.15