CS 106X: Programming Abstractions (Accelerated)

Homework

Message Forum
(do not post solution code!)

Paperless
(turn in homework)

Partner Evaluation
(fill out after each HW)

Homework Survey
(anonymous)

Output Comparison Tool

Style Guide

Honor Code: You must work individually on all homework assignments. We check against all students from this quarter and from past quarters going back many years. Violations of the Honor Code can lead to hearings with a misconduct committee. Please be careful.

Week1 Sun 12:00 PM Week1 Fri 12:00 PM No assignments have been posted yet. There will be an announcement on the main course web page when each assignment is posted.

Week10 Tue 12:00 PM

Homework 7 (Graphs): Stanford 1-2-3

due: , 6:00pm (not accepted after , 6:00pm)

For this assignment you must solve and turn in the following single problem:

Stanford 1-2-3

Week8 Mon 10:00 AM

Homework 6 (Binary Trees): 21 Questions; Huffman Encoding

due: , 6:00pm (not accepted after , 6:00pm)

For this assignment you must solve and turn in both of the following problems:

Part A:
21 Questions

Part B:
Huffman Encoding

Week6 Fri 10:00 AM

Homework 5 (Linked Lists): Patient Queue; Tiles

due: , 6:00pm (not accepted after , 6:00pm)

For this assignment you must solve and turn in both of the following problems:

Part A:
Patient Queue

Part B:
Tiles

Week5 Wed 11:00 AM

Homework 4 (Backtracking): Maze Solver; Anagrams; Boggle

due: , 6:00pm (not accepted after , 6:00pm)

For this assignment you must solve and turn in all three (3) of the following problems:

Part A:
Maze Solver

Part B:
Anagrams

Part C:
Boggle

Maze Solver: Some students on Windows machines were reporting that they could not load any files properly. The starter code was just patched on Fri 10/28 at 2:15pm to correct this issue. If you have this problem, please re-download the starter code. We are sorry for the inconvenience.

Week4 Mon 11:00 AM

Homework 3 (Recursion): Fractals; Grammar Solver; 20 Questions

due: , 6:00pm (not accepted after , 6:00pm)

For this assignment you must solve and turn in all three (3) of the following problems:

Part A:
Fractals and Graphics

Part B:
Grammar Solver

Part C:
20 Questions
(now available!)

Week2 Fri 11:00 AM

Homework 2 (ADTs): Word Ladder; N-Grams; Maze Generator

due: , 6:00pm (not accepted after , 6:00pm)

For this assignment you must solve and turn in all three (3) of the following problems:

Part A:
Word Ladder

Part B:
N-Grams

Part C:
Maze Generator

Week1 Fri 11:00 AM

Homework 1 (C++ Basics): Mad Libs; Game of Life

due: , 6:00pm (not accepted after , 6:00pm)

For this assignment you must solve and turn in both of the following problems:

Part A:
Mad Libs

Part B:
Game of Life

Mad Libs: There were small typos in the input files clothing.txt and tarzan.txt. The files were corrected on 10/1.
Mad Libs: You may assume that you won't see a token with multiple placeholders right next to each other with no spaces between, such as "<noun><noun><noun>".
Life: You may assume that the world's size is at least 3x3.
Both parts: Our output comparison tool was showing the wrong line numbers for some diffs. If the comparison tool says your output is wrong but then shows red/green lines that are the same, look 1-2 lines up or down from that place to find the actual output difference. This was caused by a bug in our library and has been fixed. Future HWs will not exhibit this bug.

()

due: ,

(not accepted after
, )

Files

spec
starter ZIP
FAQ
demo JAR
(how to run?)

Expected Output

maze01-tiny: output, DFS, BFS, Dijkstra, A*
maze04-small: output, DFS, BFS, Dijkstra, A*
maze05-medium: output, DFS, BFS, Dijkstra, A*
maze10-huge: output, DFS, BFS, Dijkstra, A*
terrain01-tiny: output, DFS, BFS, Dijkstra, A*
terrain03-small: output, DFS, BFS, Dijkstra, A*
terrain06-medium: output, DFS, BFS, Dijkstra, A*
terrain07-large: output, DFS, BFS, Dijkstra, A*
map-middleearth: output
Rauros: DFS, BFS, Dijkstra
Black Gate: DFS, BFS, Dijkstra
map-stanford: output, DFS, BFS, Dijkstra
map-usa: output
Portland/NY: DFS, BFS, Dijkstra
Bismarck/CHI: BFS
random (medium): output, screenshot

** The demo JAR looks for its input files in its current directory. If you get a file-not-found error, make sure you run the JAR from a directory that contains the input files.

Wikipedia: Huffman Encoding
Wolfram MathWorld: Huffman Encoding
ASCII table

test #1 (very short strings)
test #2 (short.txt)
test #3 (medium.txt)
test #4 (compress/decompress)
test #5 (hamlet, a big file)
test #6 (tom sawyer, even bigger)
test #7 (images and sound files)
test #8 (empty file)

PQueue test 1

Internet Anagram Server
Wikipedia: Boggle

maze #1, #2, #3, #4
anagrams #1, #2, #3, #4
boggle #1, #2, #3

Wikipedia: Backus-Naur form (BNF)
Wikipedia: Formal grammar
Java Language Specification (the grammar for Java programs)
Grammar tool (lets you make your own grammar and test it out)

Warmup Problem, Karel Goes Home: test #1
Part A, Convert String to Integer: test #1
Part A, Balancing Parentheses: test #1
Part B, Human Pyramid: test #1
Part C, Sierpinski Triangle: text: test #1; graphics: order-1, order-2, order-3, order-5
Part D, Flood Fill: text: test #1; graphics: screenshot 1, screenshot 2, screenshot 3, screenshot 4, screenshot 5
Part E, Grammar Solver: test #1, test #2, test #3
Grammar Verifier: paste your sentences and math expressions from your grammar to see if they match the proper format
(For more, run the demo)

demo JAR, Part B

Stanford C++ Lib: HashMap, HashSet, Lexicon, Map, Queue, Set, Stack
Wikipedia: N-gram
Wikipedia: Markov Chain

Part A (Word Ladder): You don't need to generate exactly the same word ladder, as long as yours is the same length.
test case #1 (code → data)
test case #2 (smalldict1.txt)
test case #3 (work → play; sleep → awake; etc.)
test case #4 (metal → azure; etc.)

Part B (N-grams): It's hard to match the expected output exactly because it is random. But you should match the overall format, intro message, etc.
test case #1 (tiny)
test case #2 (hamlet)
test case #3 (tomsawyer)
test case #4 (ladygaga)
test case #5 (tiny)
(For more, run the demo)

Stanford C++ Lib: Grid
Wikipedia: Game of Life
ConwayLife.com

test #1 (simple)
test #2 (snowflake; invalid input)
test #3 (glider)
test #4 (spiral)
test #5 (glider)
test #6 (diehard; animation)
(For more, run the demo JAR)

"I need help with my homework!"

There is probably someone in the LaIR, or maybe the instructor has office hours soon. If so, go see them.
Check the message forum; your question may have been answered there.
Go to the YEAH hours for this assignment.
Read the relevant chapters and sections of the textbook
Look at the in-class lecture examples.
Look at this week's section handout problems and their solutions.
Start early! We get swamped the day assignments are due.
Don't panic. Every student has late days that can be used to submit an assignment after the due date.

This document and its content are copyright © Marty Stepp and Victoria Kirst, 2016. All rights reserved. Any redistribution, reproduction, transmission, or storage of part or all of the contents in any form is prohibited without the authors' expressed written permission.

CS 106X: Programming Abstractions (Accelerated), Autumn 2016

Homework

Homework 7 (Graphs): Stanford 1-2-3

Homework 6 (Binary Trees): 21 Questions; Huffman Encoding

Homework 5 (Linked Lists): Patient Queue; Tiles

Homework 4 (Backtracking): Maze Solver; Anagrams; Boggle

Homework 3 (Recursion): Fractals; Grammar Solver; 20 Questions

Homework 2 (ADTs): Word Ladder; N-Grams; Maze Generator

Homework 1 (C++ Basics): Mad Libs; Game of Life

()

Files

Links

Expected Output

"I need help with my homework!"

Honor Code Reminder: