Description
• See Piazza for due date and time o Grading the next day • Submit program to perforce in your student directory o Sub directory called: /PA_Redux/… o Fill out your PA_Redux Submission Report.pdf Place it in the same directory as your solution Enter the final Changelist number of your submission Write up a quick discussion in the report • What you learned from this assignment so far
• Programming Assessment o Extra credit for PA1 – More practice with linked lists… (kind of)
• Write a single function: remove() o Signature and structure need exactly the same o Place function in file named (see supplied files): Boustrophedonic.cpp: • Function Boustrophedonic.h: • Declaration and structure struct Node { Node *pNorth; Node *pSouth; Node *pEast; Node *pWest; }
void remove( Node *head, int row, int col);
• Assumptions o Boustrophedonic list is complete and pristine before you remove one node o Only one node will be removed in the function o The head node will not be removed o The dimensions of the list are not given o Boustrophedonic list has an even number of columns o Boustrophedonic list has no restrictions on number of rows o On deletion, horizontal and vertical connections are preserved across the deleted node
Optimized C++ Programming Assignment 1
Optimized C++ PA -Redux Fall 2015 Keenan
Creating a Boustrophedonic List
Boustrophedonic – Greek word: • A method of writing shown in early Greek inscriptions, in which the lines run alternately from right to left and from left to right, as the furrows made in plowing a field, the plow passing alternately backward and forward. struct Node { Node *pNorth; Node *pSouth; Node *pEast; Node *pWest; }
• Start with the first node and continue in the Boustrophedonic path way, follow the RED LINE. o Start with the head, and sequentially go from 0 to 11 in the Boustrophedonic way
0 1 2 3
4567
8 9 10 11
a
e
head
North
West East
South
Optimized C++ Programming Assignment 2
Optimized C++ PA -Redux Fall 2015 Keenan • Next we create the vertical connections.
0 1 2 3
4567
8 9 10 11
badc
e f g h
head
• Create the vertical connections between row 0 {0,1,2,4} and row 1 {7,6,5,4}. o Find arrow a between 3 and 4. That arrow goes down, from 3 to 4. o Alternate direction of a, (a goes down in RED) b goes up YELLOW, c goes down BLUE, d goes up YELLOW. • Similar for the connections between row 1 {7,6,5,4} and row 2 {8,9,10,11} o Alternate direction of e, (e goes down in RED) f goes up YELLOW, g goes down BLUE, h goes up YELLOW.
Optimized C++ Programming Assignment 3
Optimized C++ PA -Redux Fall 2015 Keenan • Drawing the list with all the links displayed. o Each node actually has 4 pointers, most are nulls. North, South, East, West o Here the list is drawn with GREEN links showing the explicit null pointers.
0
0
0
0 0 0
00
0 0
0
0 0
0 000
0
0
0
000
0 0 0
000
0
0
head
• Rows and Columns o Rows and columns are not provided, nor are they added in the Node structure. o You need to calculate these as you walk the list. o The lists will vary in dimensions, Row x Column (row,col) o There will be an even number of columns.
(0,0) (0,1) (0,2) (0,3)
(1,3)(1,2)(1,1)(1,0)
(2,0) (2,1) (2,2) (2,3)
0
0
0
0 0 0
00
0 0
0
0 0
0 000
0
0
0
000
0 0 0
000
0
0
head
Optimized C++ Programming Assignment 4
Optimized C++ PA -Redux Fall 2015 Keenan • Deletion o Remove only one node at a time o Keep horizontal connections, through the deleted node Fix adjacent nodes connections o Keep vertical connections, through the delete node Fix adjacent nodes connections o Many examples to follow
Delete Node (1,2)
0
0
0
0 0 0
00
0 0
0
0 0
0 000
0
0
0
00
0 0 0
000
0
0
head
Delete Node (1,1)
0
0
0
0 0 0
0
0 0
0
0
0 000
0
0
0
00
0 0 0
000
0
0
head
Optimized C++ Programming Assignment 5
Optimized C++ PA -Redux Fall 2015 Keenan Delete Node (1,0) 0
0
0
0 0 0
00
0 0
0
0 0
0 000
0
0
0
00
0 0 0
000
0
head
0
Delete Node (0,2)
0
0
0
0 0
00
0 0 0 0
0 000
0
0
0
000
0 0
000
0
0
head
0
Optimized C++ Programming Assignment 6
Optimized C++ PA -Redux Fall 2015 Keenan Delete Node (0,3) 0
0
0
0 0
00
0 0
0
0 0
0 000
0
0
000
0 0
000
0
0
head
0
Delete Node (2,3)
0
0
0
0 0 0
00
0 0
0
0 0
000
0
0
0
000
0 0 0
00
0
0
head
Optimized C++ Programming Assignment 7
Optimized C++ PA -Redux Fall 2015 Keenan Delete Node (0,1) 0
0
0
0 0
00
0 0
0
0 0
0 000
0
0
0
000
0 0
000
0
0
head
Delete Node (1,3)
0
0
0
0 0 0
0
0 0
0
0
0 000
0
0
0
00
0 0 0
000
0
0
head
Optimized C++ Programming Assignment 8
Optimized C++ PA -Redux Fall 2015 Keenan Delete Node (2,0) 0
0
0
0 0 0
00
0
0
0 0
0 00
0
0
0
0
000
0 0 0
00
0
0
head
General: • Write all programs in cross-platform C or C++. o Optimize for execution speed and robustness. • Create a programming file for each problem, for example o Student directory /PA_Redux/… o Make sure that each problem can be compiled and run through the checked in solution • Do all your work by yourself o Feel free to talk with others about setup, version control, ideas o But do not copy your friend’s code. Please don’t – I can tell with my difference tools o Feel free to share ideas • Check in the problems multiple times, at least 3 times per problem o Have reasonable check-in comments o Seriously, I’m checking • Make sure that your program compiles and runs o Warning level 4, some times that is not possible due to MS headers… o Your code should be squeaky clean. • We are using Perforce o You should have received the document describing how to login. Please look at the documentation and videos under the reference directory o Submit program to perforce in your student directory Sub directory called: /PA_Redux/… • As described above o All your code must compile from perforce with no modifications. Otherwise it’s a 0, no exceptions o Only Visual Studio 2013 allowed
Optimized C++ Programming Assignment 9
Optimized C++ PA -Redux Fall 2015 Keenan
Simple check list to make sure that everything is checked in correctly • Do they compile and run without any errors? • Warning level 4 free? • Submitted it into /PA_Redux directory? • Can you delete you local drive, regrab the PA_Redux directory? o Is all the code there?
Most assignments will have hints in a section like this. • Do many little check-ins o Iteration is easy and it helps. o Perforce is good at it. • Think about performance, did you read the Code Complete chapters? o A lot of good ideas in there.