Homework 1 (due 4/7)
CSC 321

We talked about the goals of the class, and spent some time discussing examples, and using graph theory as a modeling tool. We move on to the analysis of algorithms (book pages 41/42), and we saw some basic algorithms: maximum finding (p. 561), linear search, and binary search (Section 4.1). I also mentioned the selection problem (finding the kth largest element). Next week, we will talk about asymptotic notation (Section 2.3), and continue with sorting algorithms: insertion sort, quicksort and mergesort (Chapter 5).

Handing it in: Submit to the d2l dropbox. Use some standard format for your homework (Word or pdf, for example), and make sure to include your name and assignment number. Include screenshots for code and testruns. You do not need to include the code (or any executables). Please include all material in a single file (and don't use zip). See SampleHWSubmission.docx (or SampleHWSubmission.pdf) for a sample homework. Note how I cropped and resized the screenshots to make them more readable.

When submitting programs, include text of the programs in your homework submission, together with printouts/screenshots of test-runs of your program. Unless I ask for it specifically, you do not have to submit files with program code or executables. I leave the programming language up to you, but I strongly suggest a light-weight scripting language, such as Python. This is not a programming course, so I will not be giving any programming advice. You are welcome to use the programs I show in class as starting points.

1. (Reading Assignment) Read Sections 2.1, 2.3, 2.5, and 2.6.

2. (Mode, 15pt). There are various way to define midpoints for sets of values: average, median, and mode. The mode of a list is the value that occurs most frequently in the list. E.g. the mode of [3, 4, 2, 4, 7] is 4. The mode is not necessarily unique, e.g. [2,1,3, 2,1] is bimodal: it has two modes: 1 and 2.

  1. [5pt] Implement an algorithm that finds a (any) mode of a list given as an input. Try to make it as efficient as possible. Testrun it on some sample inputs. Hint: using hash-tables will simplify your solution a bit. Keep your code simple and clean.

  2. [5pt] What is the running time of your algorithm in a? Determine your answer by counting the steps your algorithm makes, depending on the length n of your list lst.

  3. [5pt] Verify your running time analysis in b) experimentally by plotting running times for random lists of various lengths (as we have done with the max and binary search algorithms; code is available on d2l, feel free to use it as a starting point). To get interesting results, restrict the elements of the list to be integers in some restricted range (e.g. 1..100, or 1..sqrt(n) to get duplicates).

Note: include screenshots of the program, as well as testruns. Please crop the screenshots, so your code is readable.

3. (Binary Search, 10pt) You are given an ordered list, lst, of n numbers and a number x. Your goal is to determine whether x occurs in the list lst, that is, whether there is i such that lst[i] = x. You can only access the list by making queries of the form "lst[j] <= x?" and "lst[j] == x?". As we saw binary search can solve this problem making at most log n + O(1) queries. This exercise is about what happens if you get wrong answers to your queries. (How could that happens, well a noisy transmission channel, for example.)

a) [5pt] Suppose you know that there will be at most one incorrect answer to your queries. Show that you can still determine whether x occurs in the array making at most 2 log n + O(1) queries. Write pseudo-code for this problem. You can---but you don't have to---implement this. If you want to implement this, here is some code for making <= and == you can use (k counts the number of wrong answers, up to maxk; the random number generator decides, with small probability, to make an error, if the number of errors hasn't been maxed out yet):

b) [5pt] Suppose you know that the number of incorrect answers is bounded by some number maxk. Show that you can determine whether x occurs in the array/list making at most (maxk+1) log n + O(1) queries.

c) [Extra Credit Challenge, 5pt] For the case of at most one wrong answer can you do better than 2 log n + O(1) queries? (So you really have to break the factor of 2.)

4. (Modeling with Graphs, 15pt) Here is a classic puzzle:

You have a 3x4 chessboard with 3 white and 3 black knights arranged as shown above. Recall that a knight jumps two squares in one direction, and then one square orthogonally. E.g. the black knight on d2 can currently jump to b3 and b1. The white knight on a1 can reach b3 and c2. There can only be one pieces on a square at any given time. The goal of the puzzle is to exchange the positions of the white and black knights using legal knight's moves. Before doing the following problems, I suggest you set up this problem (maybe on a piece of paper and some coins of different colors/sizes for the knights), and play with it.

a) [5pt] How do you model this problem as a graph problem. That is, describe how to construct a graph for this problem that will help you solve it. Explain what the vertices and edges of the graph are, and draw the graph explicitly within the chessboard. Include a picture.

b) [4pt] Unravel the graph, redrawing it so as to show the underlying structure of the graph rather than the visual structure of the chessboard. Include the picture.

c) [3pt] Based on your redrawing in b, does the problem have a solution? If so, find a shortest solution, and list the moves in such a solution. If not, argue that there is no solution based on the properties of the graph.

d) [3pt] What about the same problem for the initial set-up shown below (on a 2x5 board). Possible, or not possible? Argue your answer briefly.

Marcus Schaefer
Last updated: April 1st, 2015.