Recent Changes - Search:
ECG Home






Fall 2017

Older Courses

Spring 2017

Fall 2016

Spring 2016

Fall 2015

Spring 2015

Fall 2014

Spring 2014

Fall 2013

Spring 2013

Fall 2012

Spring 2012

Fall 2011

Spring 2011

Fall 2010

Spring 2010

Fall 2009

Spring 2009

Fall 2008

Spring 2008

Fall 2007


edit SideBar


Home Assignments Lecture Blog Resources Discussion Group

Exam 2 is Fri Apr 24 results
Exam 1 is Fri Mar 6

Lecture videos

Right-click and open images in new tab for detail viewing.

Meeting 39: Fri May 1

Meeting 38: Wed Apr 29

Meeting 37: Mon Apr 27

Meeting 36: Fri Apr 24

  • Exam 2 administered

Meeting 35: Wed Apr 22

  • expectations for Exam 2
  • going over stdin_regex.cpp code for playing with regex's
  • to convert from smatch object to a number, use this (e.g. for element 1 of the smatch array):

Meeting 34: Fri Apr 17

  • Prof. Grinberg gave joint lecture in OS408
  • C++ regex's are compatible with JavaScript (aka ECMAScript),
  • use double-backslashes to escape characters—first backslash escapes the backslash for the C compiler, then you have the backslash to escape the char you're interested in
  • looking at rules for regex's and writing exprs for various match problems
  • different subgroups specified by parens; to match a literal paren, \\(
  • vertical-bar | to match alternative patterns
  • quantifiers *, +, ?, and {int}
  • actually writing code to do it:

Meeting 33: Wed Apr 15

  • visit by Jim Forance from Kronos
  • meeting held in Alumni Hall, no recording

Meeting 32: Mon Apr 13

  • PS6 due date extended to Wednesday
  • Exam 2 is Fri Apr 24
  • Wednesday's lecture is in Alumni Hall (will not be recorded)
  • PS7a introduction to Kronos Intouch log file project
  • let's look at some log files...
  • we will be using regular expressions and time parsing libraries
  • what are regular expressions?
  • they're parsed with finite state machines (similar to Markov models)

Meeting 31: Fri Apr 10

  • next Wed Apr 15: special guest lecture by Jim Forance (Kronos), to be held in Alumni Hall (jointly with Victor's section)
  • two different ways to use maps to hold counts of k-grams and k+1-grams
    1. flat map of k-grams and k+1-grams; search for k+1-grams by looking for them from alphabet
    2. nested maps: value of each k-gram entry is a map of k+1-gram entries
  • implementing randk
  • Attach:markov-demo.pdf notes
  • reviewing copy constructor issue from GuitarHeroLite.cpp sample code—the problem and two solutions

Meeting 30: Wed Apr 8

  • continued explanation of Markov modeling algorithm
  • figuring out order 2 model of Princeton sample string gagggagaggcgagaaa
  • using std::map to represent counts of k-grams and k+1-grams
a.k.a, dictionary or hash

Meeting 29: Mon Apr 6

  • debugging GuitarHeroLite.cpp sample code:
    • using initializer list to allow RingBuffer object (instead of pointer to RB)
    • problem with makeSamplesFromString
  • introducing Markov modeling PS6
  • will be due next Monday

Meeting 28: Fri Apr 3

  • guest lecture by Mark Sherman on music theory

Meeting 27: Wed Apr 1

  • GuitarString.hpp
  • GStest.cpp
  • GuitarHeroLite.cpp
  • intro to music theory:
    • 12 semi-tones per octave
    • each is the twelfth root of 2 apart from each other in frequency
    • e.g. if note "A" is the root, the note "E" is 7 semitones away
    • so if A is 440 Hz, E is 440 x 2 ^ (7/12) Hz
    • 2 ^ (7/12) is 1.4983, which would make the E note 659.255 Hz
    • in real music, "E" is considered the "fifth" of A, and is tuned to exactly 1.5x in freq, or 660 Hz
  • Todo: make a vector of the 37 Sound player objects, also figure out keyboard stuff

Meeting 26: Mon Mar 30

  • go over Fred's RB implementation
  • GuitarString class spec
  • using SFML to get audio from a GuitarString
  • GuitarHeroLite walk through
  • full GuitarHero assignment

Meeting 25: Fri Mar 27

  • what ones will be thrown by RingBuffer?
  • example for constructor
  • catching them in Boost testing
  • total test coverage: what does that look like?
“Your test file must exercise all methods of your ring buffer, and must exercise all exceptions.”

Meeting 24: Wed Mar 25

  • test-driven development: write tests first
    • “stub in” function implementation—e.g. get the functions to compile, just returning constant values
    • get your test to run, and fail (that's good)
    • then get your code to work
  • e.g. here is an implementation for RingBuffer.size():
    int RB::size() {
      // this is not the correct implementation;
      // should return # of elements in the ring.
      // this is correct if the RB is full.
      return _capacity;
  • and here is a test harness for it (this would go in test.cpp):
      RB rb(3);
      BOOST_CHECK(rb.size() == 0);
      BOOST_CHECK(rb.size() == 1);
      BOOST_CHECK(rb.size() == 2);
      BOOST_CHECK(rb.size() == 3);

    With the broken, stubbed-in implementation, the first three tests fail and the fourth one succeeds. With a correct implementation, they should all work.
  • Implementation discussion:
    • If using Princeton's _first and _last index variables, you also need a boolean _full to distinguish the case when _first == _last. This could either mean the ring is empty (e.g. the initial state when both indices are zero) or full (after you've enqueued enough items to wrap _last around to _first).
    • Jesse suggested using _first and _size instead. This should work without the need for a third state variable.
    • Chris asked if you can use existing data structures from STL. Fred wasn't happy about this but did not give a definitive answer. He sort of said yes, but only if you properly explain the time and space implications.
    • The goal is to have O(N) space performance for construction and any subsequent use, and O(1) performance for enqueue and dequeue.

Meeting 23: Mon Mar 23

  • PS5a assigned: Ring Buffer with cpplint, testing, and exceptions
  • from Princeton's Guitar Hero assignment
  • demo, and let's talk about sound
  • the Karplus-Strong algorithm
  • concepts involved in implementation:
    • a ring buffer (to hold the audio waveform)
    • exception handling (to fail gracefully when users make mistakes with your ring buffer API)
    • Boost unit testing (with ability to expect exceptions, and trap them if present, and fail if they are not present)
(for the full assignment)
  • SFML SoundBuffer and Sound objects
  • SFML keyboard event handling

Meeting 22: Fri Mar 13

Meeting 21: Wed Mar 11

Meeting 20: Mon Mar 9

  • PSx will be code style and opportunity to revise past work
  • PS4 due date extended to Friday
  • Attach:ps4-worksheet.pdf: Let's make sure we understand the edit distance matrix
  • after filling the matrix, walking it backward to derive path
  • if time permits: additional info about PS4 submission requirements

Meeting 19: Fri Mar 6

  • Exam 1 administered

Meeting 18: Wed Mar 4

  • continued discussion of edit distance algorithm

Meeting 18: Mon Mar 2

  • PS4 is assigned; due Wed Mar 11
  • recapping edit distance: find minimum transformation from one string to another, with penalties of 0 for exact match, 1 for replacement, and 2 for insertion
  • look at PS4 requirements: implementation, measurement of time and space, and reporting
  • data from last year's class:
  • demonstration of working code
  • recursive approach: what are the limitations?
  • dynamic programming approach: like recursion, but structure the computation so that recursive result is always available before it's needed
  • key formula from Princeton PS (let's make sure we understand this):
opt[i][j] = min { opt[i+1][j+1] + 0/1, opt[i+1][j] + 2, opt[i][j+1] + 2 }
  • N × M matrix approach (with double-walk)

Meeting 17: Fri Feb 27

  • Derrell Lipman, guest lecture, edit distance problem (PS4)
  • three examples of edit distance: what changes do I have to make to get from string s to string t?
    • copying a programming assignment, but making changes so as to hope to not get caught
    • contextual spell-correct menus
    • genome sequences
  • matching bad to sad, then bell to smell
  • operations are match, replace, and insert
  • these will have costs of 0, 1, and 2 respectively
  • computing costs of two different ways of matching bell to smell; one has cost 3, and the other, 5
  • when determining edit distance, need to find the minimum edit distance between two strings
  • let's do it recursively, using a “divide and conquer” algorithm
  • there are some cases where we know the answer—the “base cases”—let's use those to work back to the full solution
  • figuring out the base cases
    • if both strings are zero length, match cost is 0
    • if one string is zero length, match cost is # of chars in the other string x 2 (penalty per insertion)
    • if other string is zero length, match cost is # of chars in the former string x penalty of 2
  • full presentation of a recursive implementation in C
  • what's the problem with the recursion? It's not space, but time... we keep calling our recursive functions again and again with the same args
  • how to fix? answer: dynamic programming! (term has nothing to do with computer programming, but rather, keeping results in a table)
  • every time you do a calculation, store it in a table, and then if you're ever called with those same arguments and you find you have something stored there, you can just return that value, rather than doing the calculation again!

Meeting 16: Wed Feb 25

  • Fred's office hours canceled through rest of week (travel)
  • PS3b is due Monday
  • We will start PS4 (edit distance for bioinformatics) on Friday
    Fred's section will have guest lecturer—Dr. Derrell Lipman
  • big picture of physics:
    1. compute x,y forces on each body as a result of the other bodies
      (store this in a new, temporary pair of double vectors)
    2. for each body:
      • convert x,y force into x,y acceleration (based on body's own mass)
      • convert acceleration in to change in velocity (based on simulation time step)
      • update body's position based on updated velocity (and time step)
  • continuing the physics formulas; as we surmised, do not need atan2/sin/cos
  • how your class will be modified to do the physics
  • abstraction barrier—what's inside the class; what's outside

Meeting 15: Mon Feb 23

  • PS3b is assigned; due Fri Feb 27
  • std::vector<Body> vs. std::vector<Body *>
  • significance of const in method declarations; e.g.,
virtual void draw (sf::RenderTarget& target, sf::RenderStates states) const;
  • overview of physics

Meeting 14: Fri Feb 20

Meeting 13: Wed Feb 18

  • geometry of astronomical world vs. that of SFML window
  • properties of Body class: constructors, private member vars, public methods
  • no need to store sf::Vector2f's of pixel position or pixel velocity—dynamically convert from astronomical _xpos, _ypos in draw method
  • you need to store _universe_size (a radius) and _window_size to perform this conversion
  • use doubles (not floats) to represent astronomical units
  • deferring conversation of parsing world file. Recommendation: concretely instantiate earth and other bodies for first pass of your code

Meeting 12: Tue Feb 17

  • discussion of LSFR representations and efficiency tradeoffs; e.g.:
    • std::string manually copying bytes method — O(n) per step
    • std::string using substring operations — library copies bytes, plus does memory allocation — worse because of malloc
    • std::vector no malloc, but still copying bytes — O(n). (Might be better than this if vector of bools)
    • integer — no copying, just bitshifting, which is one machine instruction — O(1)
    • demonstration of speed differences
  • Intro to PS3a with live demo (go to 46:00 mark here); discussion of Newton's gravitational law; examination of planets' masses w/r/t Sun's

Meeting 11: Fri Feb 13

  • Exam 1 is Fri Mar 6
  • demo of PhotoMagic
    • with different LFSRs
  • explanation of image and file formats
  • PS2b extra credit projects
  • any other PS2a or PS2b Q&A
  • Gerry Sussman and Hal Abelson (in introduction to SICP):
    “programs must be written for people to read and only incidentally for machines to execute.”

    agree? disagree?
  • poll: what things coding standards?

Meeting 10: Wed Feb 11

  • going over some implementations
  • PS2b: implementing image encoding (and decoding) demo
  • RGB image representation
  • XOR operation is reversible (XOR to 0 does nothing; XOR to 1 inverts)
  • PS2b is due Tuesday

Meeting 9: Mon Feb 9
Lecture/discussion at

  • The Joel Test: 12 Steps to Better Code
  • example of a running main -- showing LFSR working
  • generate
  • questions about Boost—it generates a main, so when linking you can't link also with your own main. Link separately
  • your stream insertion operator should work — we'll test it on the back-end (or you can write your own tests that test it)

Meeting 8: Fri Feb 6

  • Unix is case-sensitive; main.cpp and Main.cpp are different files
    • use main1.cpp and main2.cpp (don't capitalize to distinguish versions, stylistically bad)
    • must be Makefile, not makefile (this is not style, it's what's expected by make)
  • visual diagram of Make dependencies for PS1
  • header file for LFSR
  • test driven development (TDD): write tests before you write the implementation (?!)
  • let's try it—we'll create “stubs” for our methods

Meeting 7: Wed Feb 4

Meeting 6: Mon Feb 2


  sf::Vector2f _top, _left, _right;  // my own triangle
  int _depth; 			     // my own depth
  Sierpinski* _child0;		     // my "children" -- three more tri inside
  Sierpinski* _child1;
  Sierpinski* _child2;
  • in constructor, we've set newdepth as depth - 1, and if newdepth is zero, we set all the _child ptrs to NULL. (In C++98, NULL is the right way to specify a null pointer. In C++11, it would be nullptr)
  • but if newdepth is not zero, then in constructor, instantiating children with code like:
  _child0 = new Sierpinski(_top, p1, p3, newdepth);
  _child1 = new Sierpinski(p1, _left, p2, newdepth);
  _child2 = new Sierpinski(p3, p2, _right, newdepth);
  • In destructor, destroy the child nodes with:
  if (_child1 != NULL) {
    delete (_child1);
    delete (_child2);
    delete (_child3);
  • in draw method, after drawing the upside down inner triangle, recursively descending into the three child triangles, if and only if they do not have null pointers:
  if (_child1 != NULL) {
    _child1.draw(target, states);
    _child2.draw(target, states);
    _child3.draw(target, states);
  • in Makefile, dependencies for main.o were wrong, it was missing dependency on sierpinski.hpp. That line should be:
main.o: main.cpp sierpinski.hpp
  • on initializer lists: realized that you should specify them in the order that they member variables are declared (get warning otherwise)
  • you have to create a constructor that goes along with Sierpinski(sf::Vector2f, sf::Vector2f, sf::Vector2f, int); in the header file... this will be the one used during the initial recursive process to make the tree of objects.

Meeting 5: Fri Jan 30

  • reading command line args
    • main is int main (int argc, char* argv[])
    • use atoi (or atof) to convert strings to ints (or floats)
    • other methods?
  • classes: use header files to separate interface from implementation
  • implementing sf::Drawable by providing private method:

    void virtual draw(sf::RenderTarget& target, sf::RenderStates states) const;

  • defining a class in .hpp and implementing in .cpp
  • (at least) two ways to do Sierpinski recursion:
    • build tree data structure at object initialization time; recurse down this static object-tree during drawing
      you will have to use ptrs to objects because objects don't exist yet at root-object-initialization-time
    • dynamically instantiate objects each time root object is drawn
  • sample makefile
    see and

Meeting 4: Wed Jan 28 class canceled; snow day

Meeting 3: Mon Jan 26

  • open questions / open issues?
  • poll: Your OS?

Meeting 2: Fri Jan 23

  • open questions?
  • most important: get your environment set up before Sunday night. Compile SFML's "Hello World" before Sunday night.
  • on Makefiles
    • I will teach them, don't worry!
    • Don't use Makefile for PS0 (it will confuse the autograder unless done to invisible specs)
  • on Bottlenose (
    • you must follow the instructions precisely (e.g., putting your files in a subdir named ps0) (demo: a sample submission)
    • you are encouraged to submit and resubmit as often as necessary (before due date)
    • assignments are due before class the day they're due (i.e., 9:59am)
    • only last submission will count
    • autograding is only a sanity check—all work will be reviewed by course TA per the grading rubric at the bottom of each assignment
    • late penalty is 10% per day up to 50% max
  • Configure VirtualBox and VirtualBox Hints
  • demonstration of VirtualBox
    • install Firefox: sudo apt-get install firefox
  • review PS0
  • overview of course
  • grading
  • attendance

Meeting 1: Wed Jan 21

Edit - History - Print - Recent Changes - Search
Page last modified on May 04, 2015, at 09:22 PM