Programming in Linux: CS288 Intensive Course Highlights and Project Overview

Cs288 Intensive Programming in Linux Instructor: C F Yurkoski Christopher.f.yurkowski@njit.edu Section web site: https://web.njit.edu/~yurkowsk/cs288.html Class 10 6-9-15 1

6-9-15 cfy 2

Project revu In class assignment homework Heaps & Binary trees 6-9-15 cfy 3

But first 6-9-15 cfy 4

others Brian Kernighan -> K&R, awk Ken Thompson -> Unix (w/ Dennis) james gosling -> Java Bill Joy -> vi Bjarne Stroustrup-> C++ Grace Hopper -> programming languages Richard Stallman -> GNU Linus Torvalds > Linux 6-9-15 cfy 5

Project 2, recall Given input files like you can find at: https://web.njit.edu/~yurkowsk/puzzle4 or https://web.njit.edu/~yurkowsk/puzzle2. which contain something like this, for example: +-+-+-+-+-+-+-+-+-+ | | | | | | |9| | | +-+-+-+-+-+-+-+-+-+ | | | | | | | | | | +-+-+-+-+-+-+-+ |7| | +-+-+-+-+-+-+-+-+-+ | | | | | | | | |8| +-+-+-+-+-+-+-+-+-+ I. e., they contain 10 lines of pluses and minuses like this: +-+-+-+-+-+-+-+-+-+ separated by lines which contain vertical bars and spaces or the digits 1-9, like this: | | | | |4| | |3| | You should write a C program which reads files in this format and attempts to replace the blanks with the digits 1-9, such that each digit appears in each row and each column once and only once. Obviously the originally digits cannot be changed. Note that you are being asked to read the input from a file not a URL and not from standard input. You should write your output to standard output; It should consist of exactly these elements: 1. The line: problem: 2. the table you read from the file 3. the line: solution: 4. your solution, (if one is possible) or the line: is not solvable. if no solution exist for the given input table. 6-9-15 cfy 6

For example, given an input file like the one above, your program could do this: cfy: ./solve ../public_html/puzzle4 problem: +-+-+-+-+-+-+-+-+-+ | | | | | | |9| | | +-+-+-+-+-+-+-+-+-+ | | | | | | | | | | +-+-+-+-+-+-+-+-+-+ | |1|2| | | | | | | +-+-+-+-+-+-+-+-+-+ | | | | | | | | | | +-+-+-+-+-+-+-+-+-+ | | | | |4| | |3| | +-+-+-+-+-+-+-+-+-+ | | |5| | | | | | | +-+-+-+-+-+-+-+-+-+ | | | | | | |6| | | +-+-+-+-+-+-+-+-+-+ | | | | | | | |7| | +-+-+-+-+-+-+-+-+-+ | | | | | | | | |8| +-+-+-+-+-+-+-+-+-+ solution: +-+-+-+-+-+-+-+-+-+ |1|2|3|4|5|6|9|8|7| +-+-+-+-+-+-+-+-+-+ |2|3|1|5|6|7|8|4|9| +-+-+-+-+-+-+-+-+-+ |3|1|2|6|7|8|4|9|5| +-+-+-+-+-+-+-+-+-+ |4|5|6|1|8|9|7|2|3| +-+-+-+-+-+-+-+-+-+ |5|7|8|9|4|1|2|3|6| +-+-+-+-+-+-+-+-+-+ |6|8|5|7|9|2|3|1|4| +-+-+-+-+-+-+-+-+-+ |7|9|4|8|1|3|6|5|2| +-+-+-+-+-+-+-+-+-+ |8|6|9|2|3|4|5|7|1| +-+-+-+-+-+-+-+-+-+ |9|4|7|3|2|5|1|6|8| +-+-+-+-+-+-+-+-+-+ cfy: You should check that you are passed one file name and that file can be opened for reading. Write you error messages to standard error. 6-9-15 cfy 7

Possible solution, use recursion 6-9-15 cfy 8

6-9-15 cfy 9

6-9-15 cfy 10

6-9-15 cfy 11

6-9-15 cfy 12

6-9-15 cfy 13

6-9-15 cfy 14

Homework 1 Modify your project2 so that the rules are more like actual Sudoku, that is, each digit may appear only once in each of the 9 boxes of 9 numbers, not simply once per column and per row. 6-9-15 cfy 15

ar command is used to create libraries e.g: ar -cvq cfy.a *.o -c Whenever an archive is created, an informational message to that effect is written to standard error. If the -c option is specified, ar creates the archive silently. -v Provide verbose output. -q Quickly append the specified files to the archive. If the archive does not exist a new archive file is created. 6-9-15 cfy 16

In class assignment Recall these cc options: -I -c -D -o In /tmp there are these files: /tmp/cfy/lib/cfy.a /tmp/cfy/include/header.h cfy.a contains: rw-r--r-- 98259/30 1760 Apr 12 11:27 2017 sub.o Which has this signature: void sub(int x) 6-9-15 cfy 17

Part 1 Write a program which calls sub() passing it PARAM from header.h Link it with cfy.a. make you your executable s name myprog Your main() should be compiled with the preprocessor VER2 defined. 6-9-15 cfy 18

Sample main.c #include "header.h" main(){ sub(PARAM); } 6-9-15 cfy 19

Part 2 Write a script which recompiles myprog iff header.h has changes or cfy.a has changed or your .c has changed. 6-9-15 cfy 20

Dumb version cc -D VER2 -c -I ../cfy/include main.c cc main.o ../cfy/lib/*.a -o myprog 6-9-15 cfy 21

Better version: if [ main.c -nt main.o ] || [ ../cfy/include/hdr.h -nt main.o ] then cc -D VER2 -c -I ../cfy/include main.c fi if [ main.o -nt myprog ] || [ ../cfy/lib/*.a -nt myprog ] then cc main.o ../cfy/lib/*.a -o myprog fi 6-9-15 cfy 22

6-9-15 cfy 23

Homework 2 6-9-15 cfy 24

6-9-15 cfy 31

6-9-15 cfy 32

6-9-15 cfy 33

Intro to heap operations: a=alloc (15); b=alloc(9), c=alloc(72)

a=alloc (15); b=alloc(9), c=alloc(7);free(b);alloc(4);

Considerations for alloc and free alloc() needs handle the case where it cannot fulfill a request. free() needs to consolidate adjacent free blocks.

Binary trees typedef struct tree tree; struct tree{ struct tree *smaller; struct tree *bigger; int size; char *addr; }; 44

6-9-15 cfy 45

A faster alloc and free Use a binary tree typedef struct tree tree; struct tree{ struct tree *smaller; struct tree *bigger; struct tree *prev; struct tree next; int inuse; int size; char *addr; }; 46

6-9-15 47

delete Find item to delete If node has no children, set parent pointer to NULL and free item. If node has one child, point parent to child and free item. If node has 2 children, replace the node to be deleted with the minimum value of the right subtree and delete the duplicate.

No children

One child

Two children

Homework 2 binary trees You are given: 1. this header file: https://web.njit.edu/~yurkowsk/project2/tree.h 2. and this test harness: https://web.njit.edu/~yurkowsk/project2/main.c Your goal is to implement a pair of binary tree Insert() and Delete() functions which use the function signatures for them in that header file and which successfully links with that test harness. Follow these guidelines: 1. Do not insert duplicates into tree; however, duplicates should not be considered an error, they should be ignored. 2. Do not assume the item you are being asked to delete is actually in the tree. 3. Do not assume that all the deletes will all occur after all the inserts. 4. Submit just the file containing your new Insert() and Delete() routines, not submit the test harness or header file. 5. Assume that the root of the tree on which your functions operate is a global variable named root and that it is initialized to NULL by the test harness prior to the first call to your functions. 6. You must of course also include in your file any additional utility functions you write which your functions use.

content of tree.h typedef struct tree tree; #define MAXWORD 26 struct tree{ struct tree *b4; struct tree *after; char word[MAXWORD]; }; void Insert(char *); void Delete(char *); #ifndef MAIN extern tree *root; #endif 6-9-15 cfy 55

content of test harness #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAIN 1 #include "tree.h" void printtree(); tree *root=NULL; main(int argc, char **argv) { tree *node; char buf[MAXWORD]; extern tree *root; tree *p; while((scanf("%s",buf))>0) Insert(buf); while(argc-->1) Delete(argv[argc]); printf("Print binary tree in order\n"); printtree(root); } 6-9-15 cfy 56

test harness (cont.) void printtree(tree *root){ if(root->b4!=NULL) printtree(root->b4); printf("Node is %s \n", root->word); if (root->after!=NULL) printtree( root->after); } 6-9-15 cfy 57

sample execution of test harness project>: cat - | ./bintree abc xyz 2>/dev/null abc qwe asd zxc qwe Print binary tree in order Node is asd Node is qwe Node is zxc project>: 6-9-15 cfy 58