Mach Learning and Data Mining

Prog Lang and Data Structure

Lecture 2 CSC 192 CSC 192 What are compilers? Input: Source file of computer program Output: Executable binary can be executed by a processor How do compilers work? Lexical/ Syntax Analysis Code Generation Linking .cpp .c .o, .exe Lexical/ Syntax analysis: Verifies that the program obeys the rules of the programming language. Code Generation: Creates an intermediate tree structure and generates an executable without linking. Linking: Combines the executable code from code generation with run time libraries to produce final executable file. Some 'C' Compilers GNU GCC Compiler Intel C/C++ Compiler Microsoft VC++ (You can download it for free from MSDN) Brief History of 'C' Appeared in :- 1973 Designed by :- Dennis Ritchie Dennis Ritchie Developer :- Originally: Dennis Ritchie & Bell Labs * C is Imperative , Procedural Language. A developer writes code that describes in exacting detail the steps that the computer must take to accomplish the goal. This is sometimes referred to as algorithmic programming. In contrast, a functional approach involves composing the problem as a set of functions to be executed. What is IDE? Integrated Development Environment Source Code Editor + Compiler + Debugger Example: CodeBlocks, Anjuta ,Microsoft Visual Studio Anatomy of C code directives int main(void) { Statements } Example Write a program that computes the volume of a sphere with a 12 meter radius, using the formula v= 4/3 * pi * r^3 ? Solution #include <stdio.h> #define PI 3.14159f int main(void) { float volume, radius; radius = 12.0f; volume = (4.0f / 3.0f) * PI * radius * radius * radius; printf("Volume (cubic meters): %.1f\n", volume); return 0; } Questions 1) What are directives? 2) What is function? 3) How to define a constant? --macro definition? 4) What are return types? 5) What is print formatting? 6) What is .1%f ?

CSC | 192 | Prog Lang and Data Structure | lecture notes | Lecture 2 CSC 192 CSC 192 What

What does the network compute? output units input units Output of network can be written as (with k indexing the two output units): h j ( x ) = f ( w j 0 + D X i =1 x i v ji ) o k ( x ) = g ( w k 0 + J X j =1 h j ( x ) w kj ) Network with non-linear activation function f () is a universal aproximator (esp. with increasing J ) Standard f : sigmoid/logistic, or tanh, or rectiﬁed linear (relu)

10_nn1.pdf-What does the network compute? output

kiwi banana watermelon apple mango cantaloupe grapes strawberry 0 1 2 3 4 5 6 7 8 9 ● Suppose our hash function gave us the following values: – hash("apple") = 5 hash("watermelon") = 3 hash("grapes") = 8 hash("cantaloupe") = 7 hash("kiwi") = 0 hash("strawberry") = 9 hash("mango") = 6 hash("banana") = 2 hash("honeydew") = 6 Collisions ● When two values hash to the same array location, this is called a collision ● Collisions are normally treated as “first come, first served”—the first value that hashes to the location gets it ● We have to find something to do with the second and subsequent values that hash to this same location ● What can we do when two different values attempt to occupy the same place in an array? ● Solution #1: Search from there for an empty location – Can stop searching when we find the value or an empty location – Search must be end-around ● Solution #2: Use a second hash function – ...and a third, and a fourth, and a fifth, ... ● Solution #3: Use the array location as the header of a linked list of values that hash to this location ● All these solutions work, provided: ● We use the same technique to add things to the array as we use to search for things in the array ● Suppose you want to add seagull to this hash table ● Also suppose: – hashCode(seagull) = 143 – table[143] is not empty – table[143] != seagull – table[144] is not empty – table[144] != seagull – table[145] is empty ● Therefore, put seagull at location 145 robin sparrow hawk bluejay owl . . . 141 142 143 144 145 146 147 148 . . . ● Suppose you want to look up seagull in this hash table ● Also suppose: – hashCode(seagull) = 143 – table[143] is not empty – table[143] != seagull – table[144] is not empty – table[144] != seagull – table[145] is not empty – table[145] == seagull ! ● We found seagull at location 145 robin sparrow hawk bluejay owl . . . 141 142 143 144 145 146 147 148 . . . seagull ● Suppose you want to add hawk to this hash table ● Also suppose – hashCode(hawk) = 143 – table[143] is not empty – table[143] != hawk – table[144] is not empty – table[144] == hawk • hawk is already in the table, so do nothing robin sparrow hawk seagull bluejay owl . . . 141 142 143 144 145 146 147 148 . . . ● Suppose: ● You want to add cardinal to this hash table – hashCode(cardinal) = 147 ● The last location is 148 ● 147 and 148 are occupied ● Solution: ● Treat the table as circular; after 148 comes 0 ● Hence, cardinal goes in location 0 (or 1, or 2, or ...) robin sparrow hawk seagull bluejay owl . . . 141 142 143 144 145 146 147 148

CSC | 192 | Prog Lang and Data Structure | lecture notes | kiwi banana watermelon apple m

CSC 192 Lecture 21 Advanced Use of Pointers Recap: Static duration variables are allocated in main memory and persists for the lifetime of the program Automatic duration variables are allocated on the stack and come and go as functions are called and return **the size of the allocation is required to be compile time constant** Recap: If the required size is not known until run time (for example if data of arbitrary size is being read from the user , or you are reading a file from disk) then using fixed size data objects is a bad idea and inadequate. In class (using blackboard). Relation between pointers and arrays in C ● Dynamically allocated arrays have the same advantages as dynamically allocated strings. ● The close relationship between arrays and pointers makes a dynamically allocated array as easy to use as an ordinary array. ● Although malloc can allocate space for an array, the calloc function is sometimes used instead, since it initializes the memory that it allocates. ● The realloc function allows us to make an array “grow” or “shrink” as needed. ● Suppose a program needs an array of n integers, where n is computed during program execution. ● We’ll first declare a pointer variable: int *a; ● Once the value of n is known, the program can call malloc to allocate space for the array: a = malloc(n * sizeof(int)); • Always use the sizeof operator to calculate the amount of space required for each element. In class (using blackboard) Significance of sizeof(...) on data types and pointers. ● We can now ignore the fact that a is a pointer and use it instead as an array name, thanks to the relationship between arrays and pointers in C. ● For example, we could use the following loop to initialize the array that a points to: for (i = 0; i < n; i++) a[i] = 0; ● We also have the option of using pointer arithmetic instead of subscripting to access the elements of the array. ● The calloc function is an alternative to malloc . ● Prototype for calloc : void *calloc(size_t nmemb, size_t size); ● Properties of calloc : ● Allocates space for an array with nmemb elements, each of which is size bytes long. ● Returns a null pointer if the requested space isn’t available. ● Initializes allocated memory by setting all bits to 0. ● A call of calloc that allocates space for an array of n integers: a = calloc(n, sizeof(int)); ● By calling calloc with 1 as its first argument, we can allocate space for a data item of any type: struct point { int x, y; } *p; p = calloc(1, sizeof(struct point));

CSC | 192 | Prog Lang and Data Structure | lecture notes | CSC 192 Lecture 21 Advanced Us

CSC 192 Lecture 9 Multi-Dimensional Array ● An array may have any number of dimensions. ● The following declaration creates a two-dimensional array (a matrix, in mathematical terminology): int m[5][9]; • m has 5 rows and 9 columns. Both rows and columns are indexed from 0: ● To access the element of m in row i , column j , we must write m[i][j] . ● The expression m[i] designates row i of m , and m[i][j] then selects element j in this row. ● Resist the temptation to write m[i,j] instead of m[i][j] . ● C treats the comma as an operator in this context, so m[i,j] is the same as m[j] . ● Although we visualize two-dimensional arrays as tables, that’s not the way they’re actually stored in computer memory. ● C stores arrays in row-major order, with row 0 first, then row 1, and so forth. ● How the m array is stored: ● Nested for loops are ideal for processing multidimensional arrays. ● Consider the problem of initializing an array for use as an identity matrix. A pair of nested for loops is perfect: #define N 10 double ident[N][N]; int row, col; for (row = 0; row < N; row++) for (col = 0; col < N; col++) if (row == col) ident[row][col] = 1.0; else ident[row][col] = 0.0; ● We can create an initializer for a two- dimensional array by nesting one-dimensional initializers: int m[5][9] = {{1, 1, 1, 1, 1, 0, 1, 1, 1}, {0, 1, 0, 1, 0, 1, 0, 1, 0}, {0, 1, 0, 1, 1, 0, 0, 1, 0}, {1, 1, 0, 1, 0, 0, 0, 1, 0}, {1, 1, 0, 1, 0, 0, 1, 1, 1}}; ● Initializers for higher-dimensional arrays are constructed in a similar fashion. ● C provides a variety of ways to abbreviate initializers for multidimensional arrays ● If an initializer isn’t large enough to fill a multidimensional array, the remaining elements are given the value 0. ● The following initializer fills only the first three rows of m ; the last two rows will contain zeros: int m[5][9] = {{1, 1, 1, 1, 1, 0, 1, 1, 1}, {0, 1, 0, 1, 0, 1, 0, 1, 0}, {0, 1, 0, 1, 1, 0, 0, 1, 0}}; ● If an inner list isn’t long enough to fill a row, the remaining elements in the row are initialized to 0: int m[5][9] = {{1, 1, 1, 1, 1, 0, 1, 1, 1}, {0, 1, 0, 1, 0, 1, 0, 1}, {0, 1, 0, 1, 1, 0, 0, 1}, {1, 1, 0, 1, 0, 0, 0, 1}, {1, 1, 0, 1, 0, 0, 1, 1, 1}}; ● We can even omit the inner braces: int m[5][9] = {1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1}; Once the compiler has seen enough values to fill one row, it begins filling the next. ● Omitting the inner braces can be risky, since an extra element (or even worse, a missing element) will affect the rest of the initializer.

All courses in CSC

Popular Documents