markfloryan / pdr Goto Github PK

"Write a recursive function that returns the number of 1's in the binary representation of n. Use the following fact: if n is even, the number of bits in the representation of n is the same as that in n/2; if n is odd, the number of bits is the same as that in floor(n/2) plus 1."

Clarify that this means num_ones = bitCounter(n/2) + 1, NOT num_ones = bitCounter(n/2 + 1)

As soon as I get the chance, I think I'm going to fix this by saying "if n is odd, the number of ones is the same as 1 plus the number of ones in floor(n/2)"

Moving over from aaronbloomfield#189:

Link the ssh/scp tutorial (http://aaronbloomfield.github.io/pdr/tutorials/other/ssh-scp.html) in the "Platform Architectures" section that talks about OS X users. So many questions about this!

Caught with AddressSanitizer (clang++ main.cpp binary_heap.cpp -g -fsanitize=address):
Here's main.cpp:

#include "binary_heap.h"

int main() {
  binary_heap heap;
  heap.insert(2);
  heap.insert(1);
  while (heap.size() > 1) {
    int a = heap.deleteMin();
    int b = heap.deleteMin();
    int parent = a + b;
    heap.insert(parent);
  }
}

./a.out outputs:

=================================================================
==42974==ERROR: AddressSanitizer: container-overflow on address 0x6030000002b4 at pc 0x0001024e6aac bp 0x7fff5d71bd60 sp 0x7fff5d71bd58
READ of size 4 at 0x6030000002b4 thread T0
    #0 0x1024e6aab in binary_heap::percolateDown(int) binary_heap.cpp:63
    #1 0x1024e86ff in binary_heap::deleteMin() binary_heap.cpp:56
    #2 0x1024e4549 in main main.cpp:13
    #3 0x7fffab008234 in start (libdyld.dylib:x86_64+0x5234)

0x6030000002b4 is located 4 bytes inside of 32-byte region [0x6030000002b0,0x6030000002d0)
allocated by thread T0 here:
    #0 0x10256414b in wrap__Znwm (libclang_rt.asan_osx_dynamic.dylib:x86_64h+0x6414b)
    #1 0x1024ec85c in std::__1::__split_buffer<int, std::__1::allocator<int>&>::__split_buffer(unsigned long, unsigned long, std::__1::allocator<int>&) __split_buffer:311
    #2 0x1024ea98c in std::__1::__split_buffer<int, std::__1::allocator<int>&>::__split_buffer(unsigned long, unsigned long, std::__1::allocator<int>&) __split_buffer:310
    #3 0x1024e9b61 in void std::__1::vector<int, std::__1::allocator<int> >::__push_back_slow_path<int const>(int const&) vector:1570
    #4 0x1024e768b in binary_heap::insert(int) binary_heap.cpp:29
    #5 0x1024e4502 in main main.cpp:10
    #6 0x7fffab008234 in start (libdyld.dylib:x86_64+0x5234)

HINT: if you don't care about these errors you may set ASAN_OPTIONS=detect_container_overflow=0.
If you suspect a false positive see also: https://github.com/google/sanitizers/wiki/AddressSanitizerContainerOverflow.
SUMMARY: AddressSanitizer: container-overflow binary_heap.cpp:63 in binary_heap::percolateDown(int)
Shadow bytes around the buggy address:
  0x1c0600000000: fa fa 00 00 00 fa fa fa 00 00 00 00 fa fa 00 00
  0x1c0600000010: 00 00 fa fa 00 00 00 00 fa fa fd fd fd fa fa fa
  0x1c0600000020: fd fd fd fd fa fa 00 00 00 00 fa fa 00 00 00 fa
  0x1c0600000030: fa fa 00 00 00 fa fa fa 00 00 00 00 fa fa fd fd
  0x1c0600000040: fd fa fa fa fd fd fd fd fa fa 00 00 00 fa fa fa
=>0x1c0600000050: 00 00 00 00 fa fa[04]fc fc fc fa fa fa fa fa fa
  0x1c0600000060: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x1c0600000070: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x1c0600000080: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x1c0600000090: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x1c06000000a0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==42974==ABORTING

The error comes from deleteMin where percolateDown is called after heap.pop_back() and hole == size() for a heap that has a single node. The reason why this doesn't usually error out on most runs is because the vector doesn't zero the element at that position unless it has to resize.

Changing percolateDown to use heap.at demonstrates this fact:

libc++abi.dylib: terminating with uncaught exception of type std::out_of_range: vector
Abort trap: 6

Students might notice the error if their heap elements are pointers to dynamically allocated objects. The solution is to therefore percolateDown(1) before pop_back() inside of deleteMin.

From aaronbloomfield#134:

free isn't a method in NSObject (perhaps it was at the time of writing and it isn't any more). I'm not too familiar with Objective C memory management (other than knowing it uses reference counting), but I believe that the proper way to deallocate an object created with [SomeObject new] is with the release keyword (e.g., [SomeObject release]).

From aaronbloomfield#119:

Apparently the latest version of clang can, in fact, output assembly in the Intel flavor for Mac OS X. Investigate and update the 08-x86.html slide set.

A follow-up:

It's the same as g++, i.e., it's -masm=intel. In the previous version of OS X's version of clang++ it used to be clang++ -S -mllvm --x86-asm-syntax=intel <cppfile>. Note -mllvm takes in the argument --x86-asm-syntax=intel, so it is order-specific.

Here's an example I just ran on my 2015 MacBook Pro running OS X 10.11.1.

$ clang++ -v
Apple LLVM version 7.0.0 (clang-700.0.72)
Target: x86_64-apple-darwin15.0.0
Thread model: posix
$ cat test.cpp
#include<iostream>

int main() {
    int z = 10;
    int *y = &z;
    int x = 3 + *y;
    std::cout << x << std::endl;
    return 0;
}
$ clang++ -m32 -S -masm=intel test.cpp
$ mv test.s test-masm.s
$ clang++ -m32 -S -mllvm --x86-asm-syntax=intel test.cpp
$ diff test-masm.s test.s
$

Some external sources:

• http://stackoverflow.com/questions/199966/how-do-you-use-gcc-to-generate-assembly-code-in-intel-syntax
• http://stackoverflow.com/questions/10990018/how-to-generate-assembly-code-with-clang-in-intel-syntax

Another follow-up:

This did not get completed in time for the spring 2016 semester. We are moving to 64-bit assembly for the fall. So changing the target date for this to the fall 2016 semester, although it may not be relevant due to the assembly flavor switch

From aaronbloomfield#145:

give an example in the big-Theta slide set with something that uses more/different variables than just 'n'

Links in lab 1 need to be changed from aaronbloomfield to markfloyan.

From aaronbloomfield#93:

There is too much content early in the semester to reliably get through in time for the labs; some of it should be moved later. Also, there is some extra time at the end of the semester (after the end of graphs) that additional content can either be created for, or existing content moved to.

Presumably, students taking 2150 have had some prior exposure to class-based inheritance. By discussing its usage in C++ at a higher level earlier in the course, they will be free to use it. For example in lab 3, they can inherit from a LinkedList to implement a Stack, or in lab 5 inherit from a BinarySearchTree to implement an AVLTree.

Discussion of virtual method tables can still be deferred to the assembly lab, if we feel that vtables are better understood in the context of compiler internals and code generation. However, features like multiple inheritance and dynamic dispatch can still be discussed at the language level.

Introduce the std=c++11 flag much earlier in the course so students can use those features. Server already uses those so no need to change anything on the backend.

Simplest: Add a remove from tail method they can use for the stick implementation.
Or...change remove to use a ListItr

Generally, the chosen methods for the Linked List are a little bit nonsensical. Let's review and redo those a bit.

Another issue with Prelab 10 is that the files on the course wiki have unix line endings, while the files we ran on the server appear to have DOS line endings. This is the cause of a fair number of the support requests, but we did tell them in the lab that they need to ignore any non-printable characters, not just tab/newline.

I've been going through the support requests on Prelab 10, downloading/running the code people say doesn't work, finding where it messes up on handling DOS line endings, and writing up a short summary on the support request. I'm leaving them all as "pending," but I'm hoping to do a bit of preliminary work to save you two some time. :P

--Andrew

From aaronbloomfield#32:

some of them (such as on graphs) need more online sources

A follow-up:

From a not-so-anonymous feedback on 4-20-14:

I find thoroughly understanding the concepts behind the lab (before I start coding) help me in getting my program correct the first (,or second, or third) time around much easier. However, sometime the material on the lecture slides just isn't sufficient. Now then, occasionally you will include links to brief articles (which are usually helpful), but they are not nearly enough information. Couple this with the fact that this class doesn't have a standard textbook to refer to, it shouldn't come as a surprise that many students will become frustrated trying to do these labs. Just recently I tried using the UVA Library system as my secondary source of information (for the Huffman Encoding Lab), and found it to be quite the powerful tool. Any student at uva has access to "virgo", which can link you to online textbooks (and direct you to local libraries that hold hard copies of these books), some of which are dedicated entirely to certain topics, such as huffman encoding/decoding. For example, I stumbled across the book "Introduction to Data Compression", by Khalid Sayood, and found it to be very helpful in completing my lab http://site.ebrary.com/lib/uvalib/docDetail.action?docID=10216746 I suppose the point I am trying to get at here is that as UVA students (and by paying tuition), we are given access to a very powerful tool. I think that it would be very helpful if you would, in addition to your links to wiki articles, include links to relevant online texts (which a student could use to better understand the lab material/concepts, or even pursue further understanding out of interest) in your lab guidelines and on your slides.

Remove the requirement that the students implement only a pointer based stack for the post-lab.

Moving from aaronbloomfield#186:

We should specify whether find() may be called to look for a string that isn't in the tree. If it can, then we need to specify what to do with "LeftLinksFollowed" and "RightLinksFollowed" (i.e. do we count one more link to reach the "null" terminator, or no?)

Some slides (e.g., 01-cpp.html) contain red text on a black background (e.g., when a value is changed during an example) and may be very unfriendly to our color-blind friends. Suggest making them bigger and bolder to accentuate instead.

Moving from aaronbloomfield#188:

The postlab for hashlab seems to have a contradiction in its timing instructions. It says:

You can do this [timing] on any machine and data files, just use the same machine and files for all tests. Be sure to specify which files and machine you used. Show timing results (use the timer placement as we used in lab) for: [continued]

However, earlier it says:

When reporting times for the post-lab report, all times must be with the words2.txt and 300x300.grid.txt files as the input. All programs must be compiled with -O2. You can do this on any computer, but make sure all your times are done on the same computer for comparison consistency. The timing code must be as specified in the pre-lab section (i.e. around the hash table usage, not the hash table creation).

Read the title.

Under Print Output Format, the examples for Postfix format and Prefix format don't have a whitespace character at the end.

Postfix format: 34 6 + -8 4 / -
Prefix format: - + 34 6 / -8 4

However, the Sample Execution Run does in fact include a trailing whitespace character for the Expression tree prefix and postfix expression.

Expression tree in postfix expression: 34 6 + -8 4 / - 
Expression tree in prefix expression: - + 34 6 / -8 4 

(Try highlighting the above lines to see what I'm referring to).

Considering that the standard version for pre-order and post-order traversal leads one to emit a trailing whitespace, it may be a good idea to mention that a trailing whitespace character is mandatory for printPrefix and printPostfix. I'm not sure how pedantic the submission server is in validating spaces, but the current situation could lead to ambiguity in the future.

The correct command for displaying the values in registers should be "register read" under the section "Assembly-specific commands".

if n is even, the number of bits in the representation of n is the same as that in n/2;

This is fine

if n is odd, the number of bits is the same as that in floor(n/2) plus 1.

This sounds like it is saying that if n is odd, the number of bits is numberOfBits(floor(n/2) + 1). This sentence should be reworded to say:

if n is odd, the number of bits is the same as 1 plus that in floor(n/2).

Slide set 5: Trees (version from Reiss's lectures (PDF))

The trees diagrams were generated from the files described here
The tree animation site is here (mirror)

AVL tree animation links are broken/java applets don't work on newer browsers.
Maybe add this link instead?
https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

in README, link for utils md goes to tutorials md

Seems the terminology for full and complete binary tree may be off. Look into this and fix.

From aaronbloomfield#154:

There exists a known IBCM file that is accepted by the simulator but not the C++ executable (or vice-versa). See course manager regrade 2533

From aaronbloomfield#158:

From a student:

In class today, you mentioned that you weren't sure about the output from clang++ using the -mllvm --x86-asm-syntax=intel flags or g++ using the -m32 -masm=intel flags on Mac OSX.

If you're interested, I have attached the outputs I received when compiling a basic C++ program (also attached) using the aforementioned flags. I used a 2014 MacBook Air running version 10.11.3 of OS X El Capitan.

Since the course is going to switch to 64-bit assembly, this may or may not be relevant in the fall. In either case, updating the 32-bit x86 slides (which are going to be kept in the repo) is not a bad idea.

From aaronbloomfield#150:

• it still says you need cs2110 for cs3330, when you need cs2150
• add more courses into the bigger graph

A follow-up:

How many more courses do we want in the bigger graph? (10 more? 20 more? 100 more?) I ask because scraping the registrar's webpage and using a large number of classes as input could be feasible (at least for input generation--not sure about grading). 😛

From aaronbloomfield#148:

In the fall, this can go in the week of fall break (just have a post-lab that week). In the spring, this can go either as part of lab 10, or as the last partial week of the semester.

From aaronbloomfield#179:

... the examples are all 32-bit examples, and should be updated to 64-bit (or perhaps have both)

From aaronbloomfield#7:

this is for the slides as well as the lab; the diagrams used in the past (and the scanned weiss pages) can't be included in this repo

A follow-up:

Need this (And related aaronbloomfield#8) be a resource from somewhere else (an open textbook / course), or a new resource entirely?

MIT and Stanford are probably good places to look for the former.

Another follow-up:

http://what-if.xkcd.com/34/ is also probably a good place to start.

Another follow-up:

Simple, untested minheap implementation at https://gist.github.com/cceckman/10027669. Uses vector for storage (students may not be familiar with push/pop.)

Another follow-up:

A new example (of "if it is to be, it is up to me") was created, along with all the huffman coding steps. There are other things that need to be worked on, though, but they will likely go into the book (and not the slides), so I am changing the label after this comment (from "fix for spring 2014" to "textbook")

Another follow-up:

@cceckman's content has been integrated into the huffman branch, but needs editing before release

From aaronbloomfield#180:

http://godbolt.org/ is a website which live-compiles entered C++ to various assembly languages via a selection of compilers. More importantly, it uses color-matched highlighting to show how C++ statements map to assembly lines. Although this could make the assembly labs too easy, I wonder if it could be used to help explain more advanced concepts to the students in the labs.

A follow-up:

I just quickly wrote up a program that would need a VMT; it really clearly highlights where the function call is occurring and how you have to navigate to the VMT to figure out which function to call. The VMT itself is also included if you don't filter assembler directives, which is pretty cool.

My code if you want to run this on your own:

class Student {
  public:
  virtual int foo() {
    return 2;
  }
};
class Bar : public Student {
  public:
  virtual int foo() {
    return 5;
  }
};

// Type your code here, or load an example.
int square(int num) {
  	Student* s;
    if (num % 2)
      s = new Student;
  	else
      s = new Bar;
  	
    return s->foo();
}

While we're on the topic tools for the assembly labs: PEDA is a nice extension for GDB that shows what's on the stack in a nice (ASCII) pictorial form. I don't know if we want to install this by default (people might conflate the features of the extension with GDB itself), but it could be a "recommended resource."

From aaronbloomfield#68:

Style guides are important to good software engineering at scale. They help programmers to produce shareable and less-buggy code, and they encourage programmers to think about language design and capabilities.

As far as I recall, style guides aren't covered in the UVA curriculum. They are a more software-engineering-oriented topic than many things in this course; however, I think they would fit in well in explaining some of the patterns (INCLUDE guards, file breakup, references v. const references v. pointers). Also (in my limited experience) there's more variety in C/C++ style guides than in Java, so covering them in 2150 could help.

Some examples: http://google-styleguide.googlecode.com/svn/trunk/cppguide.html (I like the "don't use non-const references" rule.) http://lars-lab.jpl.nasa.gov/JPL_Coding_Standard_C.pdf

A follow-up:

Let me ponder this for a bit. It would definitely fit in the capstone course, and I want to think about how best to present this in PDR...

Another follow-up:

I agree with @cceckman. It is worth considering because I've heard there might have been students in the past who don't know what tabs are (or even as extreme as writing everything on one line).

It's worth enforcing some semblance of style -- i.e., "if your code is unreadable, -5" or something. I know Sherriff and Horton used a similar rule (for unformatted code) in 1110 and 2110.

"Your task is to implement the binary bit counter function that takes in a single command-line value (which is a standard base-10 integer) and prints out the number of bits contained therein."

Should be changed to "number of ones", not "number of bits".

From aaronbloomfield#157:

Objective C is a bit outdated. Do we keep it in, as a means to show another way to add objects to C? If it is kept in, then ensure the lab machines and the VB image can properly compile it.

A follow-up:

I argue that you should keep it in to as you stated "show another way to add objects to C". Plenty of businesses still use Objective-C due to large, legacy codebases, so it is still useful to gain exposure.

Another follow-up:

Relevant Spring 2016 Piazza posts on Objective C compatibility with lab machines and VB image: Lab machine troubles, VB image troubles

From aaronbloomfield#181:

... apparently on a mac, the pointer fields are automatically initialized to null, so the students aren't doing that themselves. Then it seg faults on our (Linux) server, and they complain that it works fine for them. Put a big warning to this effect in either (or both) the tutorial and the lab.

From aaronbloomfield#121:

• have a diagram that shows how C-style strings work for the compare_string() function
• have a diagram that shows what the stack looks like for the fib() function
• add a diagram about the little-Endian addressing benefits

A follow-up:

This did not get completed in time for the spring 2016 semester. We are moving to 64-bit assembly for the fall. So changing the target date for this to the fall 2016 semester, although it may not be relevant due to the assembly flavor switch

Lab requires students to read over but not encode non-readable characters. One test case helping them test for this would be helpful.

For mergesort, add hint that they should use shr or sar instead of idiv.

@apnorton created aaronbloomfield#185 -- I've asked that it be targeted here, but in case it isn't, be sure to merge in those changes.