http://www.informit.com/store/algorithms-video-lectures-24-part-lecture-series-9780134384436
Category Archives: cos 226
COS 226 Data Structures Programs github
https://github.com/kevin-wayne/algs4/tree/master/src/main/java/edu/princeton/cs/algs4
COS 126 Python Language
Python Programs in the Textbook
Booksite Modules
Below is a table of the booksite modules that we use throughout the textbook and booksite and beyond.
| SECTION | MODULE | DESCRIPTION |
|---|---|---|
| 1.5 | stdio.py | functions to read/write numbers and text from/to stdin and stdout |
| 1.5 | stddraw.py | functions to draw geometric shapes |
| 1.5 | stdaudio.py | functions to create, play, and manipulate sound |
| 2.2 | stdrandom.py | functions related to random numbers |
| 2.2 | stdarray.py | functions to create, read, and write 1D and 2D arrays |
| 2.2 | stdstats.py | functions to compute and plot statistics |
| 3.1 | color.py | data type for colors |
| 3.1 | picture.py | data type to process digital images |
| 3.1 | instream.py | data type to read numbers and text from files and URLs |
| 3.1 | outstream.py | data type to write numbers and text to files |
If you followed the instructions provided in this booksite (for Windows, Mac OS X, or Linux), then the booksite modules are installed on your computer. If you want to see the source code for the booksite modules, then click on the links in the above table, or download and unzip stdlib-python.zip.
Programs and Data Sets in the Textbook
Below is a table of the Python programs and data sets used in the textbook. Click on the program name to access the Python code; click on the data set name to access the data set; read the textbook for a full discussion. You can download all of the programs as introcs-python.zip and the data as introcs-data.zip.
| 1 | ELEMENTS OF PROGRAMMING | DATA | |
|---|---|---|---|
| 1.1.1 | helloworld.py | Hello, World | – |
| 1.1.2 | useargument.py | using a command-line argument | – |
| 1.2.1 | ruler.py | string concatenation example | – |
| 1.2.2 | intops.py | integer operators | – |
| 1.2.3 | floatops.py | float operators | – |
| 1.2.4 | quadratic.py | quadratic formula | – |
| 1.2.5 | leapyear.py | leap year | – |
| 1.3.1 | flip.py | flipping a fair coin | – |
| 1.3.2 | tenhellos.py | your first loop | – |
| 1.3.3 | powersoftwo.py | computing powers of two | – |
| 1.3.4 | divisorpattern.py | your first nested loops | – |
| 1.3.5 | harmonic.py | harmonic numbers | – |
| 1.3.6 | sqrt.py | Newton's method | – |
| 1.3.7 | binary.py | converting to binary | – |
| 1.3.8 | gambler.py | gambler's ruin simulation | – |
| 1.3.9 | factors.py | factoring integers | – |
| 1.4.1 | sample.py | sampling without replacement | – |
| 1.4.2 | couponcollector.py | coupon collector simulation | – |
| 1.4.3 | primesieve.py | sieve of Eratosthenes | – |
| 1.4.4 | selfavoid.py | self-avoiding random walks | – |
| 1.5.1 | randomseq.py | generating a random sequence | – |
| 1.5.2 | twentyquestions.py | interactive user input | – |
| 1.5.3 | average.py | averaging a stream of numbers | – |
| 1.5.4 | rangefilter.py | a simple filter | – |
| 1.5.5 | plotfilter.py | standard input to draw filter | usa.txt |
| 1.5.6 | bouncingball.py | bouncing ball | – |
| 1.5.7 | playthattune.py | digital signal processing | elise.txt ascale.txt stairwaytoheaven.txt entertainer.txt firstcut.txt freebird.txt looney.txt |
| 1.6.1 | transition.py | computing the transition matrix | small.txt medium.txt |
| 1.6.2 | randomsurfer.py | simulating a random surfer | – |
| 1.6.3 | markov.py | mixing a Markov chain | – |
| 2 | FUNCTIONS | DATA | |
| 2.1.1 | harmonicf.py | harmonic numbers (revisited) | – |
| 2.1.2 | gauss.py | Gaussian functions | – |
| 2.1.3 | coupon.py | coupon collector (revisited) | – |
| 2.1.4 | playthattunedeluxe.py | play that tune (revisited) | elise.txt ascale.txt stairwaytoheaven.txt entertainer.txt firstcut.txt freebird.txt looney.txt |
| 2.2.1 | gaussian.py | Gaussian functions module | – |
| 2.2.2 | gaussiantable.py | sample Gaussian client | – |
| 2.2.3 | sierpinski.py | Sierpinski triangle | – |
| 2.2.4 | ifs.py | iterated function systems | sierpinski.txt barnsley.txt coral.txt culcita.txt cyclosorus.txt dragon.txt fishbone.txt floor.txt koch.txt spiral.txt swirl.txt tree.txt zigzag.txt |
| 2.2.5 | bernoulli.py | Bernoulli trials | – |
| 2.3.1 | euclid.py | Euclid's algorithm | – |
| 2.3.2 | towersofhanoi.py | towers of Hanoi | – |
| 2.3.3 | beckett.py | Gray code | – |
| 2.3.4 | htree.py | recursive graphics | – |
| 2.3.5 | brownian.py | Brownian bridge | – |
| 2.4.1 | percolationv.py | vertical percolation detection | test5.txt test8.txt |
| 2.4.2 | percolationio.py | percolation support functions | – |
| 2.4.3 | visualizev.py | vertical percolation visualization client | – |
| 2.4.4 | estimatev.py | vertical percolation probability estimate | – |
| 2.4.5 | percolation.py | percolation detection | test5.txt test8.txt |
| 2.4.6 | visualize.py | percolation visualization client | – |
| 2.4.7 | estimate.py | percolation probability estimate | – |
| 3 | OBJECT ORIENTED PROGRAMMING | DATA | |
| 3.1.1 | potentialgene.py | potential gene identification | – |
| 3.1.2 | chargeclient.py | charged particle client | – |
| 3.1.3 | alberssquares.py | Albers squares | – |
| 3.1.4 | luminance.py | luminance library | – |
| 3.1.5 | grayscale.py | converting color to grayscale | mandrill.jpg mandrill.png darwin.jpg darwin.png |
| 3.1.6 | scale.py | image scaling | mandrill.jpg mandrill.png darwin.jpg darwin.png |
| 3.1.7 | fade.py | fade effect | mandrill.jpg mandrill.png darwin.jpg darwin.png |
| 3.1.8 | potential.py | visualizing electric potential | charges.txt |
| 3.1.9 | cat.py | concatenating files | in1.txt in2.txt |
| 3.1.10 | stockquote.py | screen scraping for stock quotes | – |
| 3.1.11 | split.py | splitting a file | djia.csv |
| 3.2.1 | charge.py | charged-particle data type | – |
| 3.2.2 | stopwatch.py | stopwatch data type | – |
| 3.2.3 | histogram.py | histogram data type | – |
| 3.2.4 | turtle.py | turtle graphics data type | – |
| 3.2.5 | koch.py | Koch curve | – |
| 3.2.6 | spiral.py | spira mirabilis | – |
| 3.2.7 | drunk.py | drunken turtle | – |
| 3.2.8 | drunks.py | drunken turtles | – |
| 3.2.9 | complex.py | complex number data type | – |
| 3.2.10 | mandelbrot.py | Mandelbrot set | – |
| 3.2.11 | stockaccount.py | stock account data type | turing.txt |
| 3.3.1 | complexpolar.py | complex numbers (revisited) | – |
| 3.3.2 | counter.py | counter data type | – |
| 3.3.3 | vector.py | spatial vector data type | – |
| 3.3.4 | sketch.py | sketch data type | genome20.txt |
| 3.3.5 | comparedocuments.py | similarity detection | documents.txt constitution.txt tomsawyer.txt huckfinn.txt prejudice.txt djia.csv amazon.html actg.txt |
| 3.4.1 | body.py | gravitational body data type | – |
| 3.4.2 | universe.py | n-body simulation | 2body.txt 3body.txt 4body.txt 2bodytiny.txt |
| 4 | DATA STRUCTURES | DATA | |
| 4.1.1 | threesum.py | 3-sum problem | 8ints.txt 1kints.txt 2kints.txt 4kints.txt 8kints.txt 16kints.txt 32kints.txt 64kints.txt 128kints.txt |
| 4.1.2 | doublingtest.py | validating a doubling hypothesis | – |
| 4.1.3 | timeops.py | timing operators and functions | – |
| 4.1.4 | bigarray.py | discovering memory capacity | – |
| 4.2.1 | questions.py | binary search (20 questions) | – |
| 4.2.2 | bisection.py | binary search (inverting a function) | – |
| 4.2.3 | binarysearch.py | binary search (sorted array) | emails.txt white.txt |
| 4.2.4 | insertion.py | insertion sort | tiny.txt tomsawyer.txt |
| 4.2.5 | timesort.py | doubling test for sorting functions | – |
| 4.2.6 | merge.py | mergesort | tiny.txt tomsawyer.txt |
| 4.2.7 | frequencycount.py | frequency counts | leipzig100k.txt leipzig200k.txt leipzig1m.txt |
| 4.3.1 | arraystack.py | stack (resizing array implementation) | tobe.txt |
| 4.3.2 | linkedstack.py | stack (linked list implementation) | tobe.txt |
| 4.3.3 | evaluate.py | expression evaluation | expression1.txt expression2.txt |
| 4.3.4 | linkedqueue.py | queue (linked list implementation) | tobe.txt |
| 4.3.5 | mm1queue.py | M/M/1 queue simulation | – |
| 4.3.6 | loadbalance.py | load balancing simulation | – |
| 4.4.1 | lookup.py | dictionary lookup | amino.csv djia.csv elements.csv ip.csv ip-by-country.csv morse.csv phone-na.csv |
| 4.4.2 | index.py | indexing | mobydick.txt tale.txt |
| 4.4.3 | hashst.py | hash symbol table data type | – |
| 4.4.4 | bst.py | BST symbol table data type | – |
| 4.5.1 | graph.py | graph data type | tinygraph.txt |
| 4.5.2 | invert.py | using a graph to invert an index | tinygraph.txt movies.txt |
| 4.5.3 | separation.py | shortest-paths client | routes.txt movies.txt |
| 4.5.4 | pathfinder.py | shortest-paths client | – |
| 4.5.5 | smallworld.py | small-world test | tinygraph.txt |
| 4.5.6 | performer.py | performer-performer graph | tinymovies.txt moviesg.txt |
COS 226 Creative Programming Assignments
Below are links to a number of creative programming assignments that we've used at Princeton. Some are from COS 126: Introduction to Computer Science; others are from COS 226: Data Structures and Algorithms. The main focus is on scientific, commercial, and recreational applications. The assignments are posed in terms of C or Java, but they could easily be adapted to C++, C#, Python, or Fortran 90.
| Assignment | Description | Concepts | Difficulty |
| SCIENTIFIC COMPUTING | |||
|---|---|---|---|
| Guitar Hero [checklist] |
Simulate the plucking of a guitar string using the Karplus-Strong algorithm. | objects, ring buffer data type, simulation | 5 |
| Digital Signal Processing [checklist] |
Generate sound waves, apply an echo filter to an MP3 file, and plot the waves. | data abstraction, arrays | 5 |
| Percolation [checklist] |
Monte Carlo simulation to estimate percolation threshold. | union-find, simulation | 5 |
| Global Sequence Alignment [checklist] |
Compute the similarity between two DNA sequences. | dynamic programming, strings | 5 |
| N-Body Simulation [checklist] |
Simulate the motion of N bodies, mutually affected by gravitational forces, in a two dimensional space. | simulation, standard input, arrays | 3 |
| Barnes-Hut [checklist] |
Simulate the motion of N bodies, mutually affected by gravitational forces when N is large. | quad-tree, analysis of algorithms, data abstraction | 8 |
| Particle Collision Simulation | Simulate the motion of N colliding particles according to the laws of elastic collision. | priority queue, event-driven simulation | 7 |
| Atomic Nature of Matter [checklist] |
Estimate Avogadro's number using video microscopy of Brownian motion. | depth-first search, image processing, data abstraction, data analysis | 8 |
| Root Finding [checklist] |
Compute square roots using Newton's method. | loops, numerical computation | 2 |
| Cracking the Genetic Codes [checklist] |
Find the genetic encoding of amino acids, given a protein and a genetic sequence known to contain that protein. | strings, file input | 5 |
| RECREATION | |||
|---|---|---|---|
| Mozart Waltz Generator | Create a two-part waltz using Mozart's dice game. | arrays | 3 |
| Rogue [checklist] |
Given a dungeon of rooms and corridors, and two players (monster and rogue) that alternate moves, devise a strategy for the monster to intercept the rogue, and devise a strategy for the rogue to evade the monster. | graph, breath first search, depth first search, bridges | 8 |
| 8 Slider Puzzle [checklist] |
Solve Sam Loyd's 8 slider puzzle using AI. | priority queue, A* algorithm | 5 |
| GRAPHICS AND IMAGE PROCESSING | |||
|---|---|---|---|
| Mandelbrot Set [checklist] |
Plot the Mandelbrot set. | functions, arrays, graphics | 3 |
| H-tree [checklist] |
Draw recursive patterns. | recursion, graphics | 3 |
| Sierpinski Triangle [checklist] |
Draw recursive patterns. | recursion, graphics | 3 |
| Collinear Points [checklist] |
Given a set of Euclidean points, determine any groups of 4 or more that are collinear. | polar sorting, analysis of algorithms | 4 |
| Smallest Enclosing Circle [checklist] |
Given a set of Euclidean points, determine the smallest enclosing circle. | computational geometry, randomized algorithm | 8 |
| Planar Point Location [checklist] |
Read in a set of lines and determine whether two query points are separated by any line. | computational geometry, binary tree | 6 |
| COMBINATORIAL OPTIMIZATION | |||
|---|---|---|---|
| Small World Phenomenon | Use the Internet Movie Database to compute Kevin Bacon numbers. | graph, breadth-first search, symbol table | 7 |
| Map Routing | Read in a map of the US and repeatedly compute shortest paths between pairs of points. | graph, Dijkstra's algorithm, priority queue, A* algorithm. | 7 |
| Bin Packing | Allocate sound files of varying sizes to disks to minimize the number of disks. | priority queue, binary search tree, approximation algorithm | 5 |
| Traveling Salesperson Problem | Find the shortest route connecting 13,509 US cities. | linked list, heuristics | 5 |
| Open Pit Mining | Given an array of positive and negative expected returns, find a contiguous block that maximizes the expected profit. | divide-and-conquer, analysis of algorithms | 5 |
| Baseball Elimination | Given the standings of a sports league, determine which teams are mathematically eliminated. | reduction, max flow, min cut | 3 |
| Assignment Problem | Solve the assignment problem by reducing it to min cost flow. | reduction, min cost flow | 3 |
| Password Cracking | Crack a subset-sum password authentication scheme. | hashing, space-time tradeoff | |
| TEXT PROCESSING | |||
|---|---|---|---|
| Natural Language Modeling | Create a Markov model of an input text and use it to automatically generate stylized pseudo-random text. | suffix sorting or hashing | 6 |
| Natural Language Modeling | Create a Markov model of an input text and use it to automatically generate stylized pseudo-random text. | Markov chains, graph | 4 |
| Markovian Candidate [checklist] |
Create a Markov model of an input text to perform speech attribution. | artificial intelligence, symbol table | 6 |
| Word Searching | Search for words horizontally, vertically and diagonally in a 2D character array | tries | 7 |
| Redundancy Detector | Find the longest repeated sequence in a given text. | suffix sorting, strings | 4 |
| Text Indexing | Build an inverted index of a text corpus and find the position of query strings in the text. | suffix sorting or binary search tree | 4 |
| COMMUNICATION | |||
|---|---|---|---|
| Linear Feedback Shift Register | Encrypt images using a linear feedback shift register. | objects, encryption | 4 |
| Pictures from Space | Detect and fix data errors in transmission using a Hadamard code. | 2D arrays, error-correcting codes | 3 |
| Prefix Free Codes | Decode a message compressed using Huffman codes. | binary trees, data compression | 4 |
| Burrows-Wheeler | Implement a novel text compression scheme that out-compresses PKZIP. | suffix sorting, arrays, data compression | 7 |
| RSA Cryptosystem | Implement the RSA cryptosystem. | big integers, repeated squaring, analysis of algorithms | 8 |
| DISCRETE MATH | |||
|---|---|---|---|
| Linked List Sort | Shellsort a linked list. | linked list, shellsort | 4 |
| Batcher Sort | Implement Batcher's even-odd mergesort. | divide-and-conquer, parallel sorting hardware | 6 |
| Rational Arithmetic | Implement a Rational number data type. | struct, data abstraction, Euclid's algorithm | 3 |
| Factoring | Factor large integers using Pollard's rho method. | big integers, Euclid's algorithm | 5 |
| Deques and Randomized Queues | Create deque and randomized queue ADTs. | abstract data types, generics | 5 |
| Linear Congruential Random Number Generator | Find the cycle length of a pseudo-random number generator using Floyd's algorithm. | loops, mod | 2 |
| Stock Market | Predict the performance of a stock using Dilbert's rule. | loops | 2 |
| Subset Sum | Partition the square roots of 1 to 100 into two subsets so that their sum is as close as possible to each other. | various | 6 |
| Loops and Conditionals | Binary logarithm, checkerboard pattern, random walk, Gaussian distribution. | loops and conditionals | 1 |
Here are some Nifty Assignments created by instructors at other universities. They are more oriented towards recreational applications, but are fun and creative.
Copyright © 2000–2019 Robert Sedgewick and Kevin Wayne. All rights reserved.