Edição atual tal como às 10h58min de 31 de outubro de 2019

////////// Under Construction //////////

This is the main page of a graduate level course in computational geometry being taught in 2019/2 at the Polytechnic Institute IPRJ/UERJ. It is generally useful for programmers at the advanced level in the fields of machine learning, scientific simulations, graphics, computer vision and and multimedia programming.

General Info

• Instructor: prof. Ricardo Fabbri, Ph.D. Brown University
• Meeting times: Wednesdays 7:50-11:30, Thursdays 7:50-9:40, and 15:00-17:00, room 110.
• Evaluation criteria: at least 2 quizzes (40%), practical projects (60%).
• Forum for file exchange and discussion: email and IRC #labmacambira

Lecture Log

Part 1: C++ Programming Practice and Review

Wed 9Out19 (twice lecture load)

• Hello world
  • for loop print 10x
• Slides 1 Review C Fabbri
  • Variables, arrays/vectors
• Farenheit to/from celcius program: homework

Wed 16Oct19

• Show results of Farenheit to Celsius
• Learn Codeblocks

Thu 17Oct19

• Print function graph (K&R Histogram)
  • Horizontal
    • Learn how to write max function: non-recursive and recursive
    • Learn first simple sort algorithm using max

Wed 23Out19 (twice lecture load)

• Due: simple sort using max
• bucket sort (class exercise). Due. (student juliana: done)
• Other simple sorts. Insertion, selection, bubble
  • Basic building block: insert on sorted array, keeping it sorted
• Theory: arrays.

Thu 24Out19

• Overdue: simple sort using max
  • Did: used max function
    • at first, max function without index
      • Sub-exercise: implement max of an array to return index, recursive and non-recursive
    • did: sort with max function, with index
  • Question: does it work with repeated entries?
  • If you have a vector of float height[num_people] and age[num_people], and there is a repeated age, can you print ages and respective heights sorted by age, without losing information?
  • What is a stable sort
• Vector and cross product exercise
  • Exercise from qualify
• Sort building blocks

Wed 30Out19

• Overdue: Vertical Function graph (K&H Histogram)
• Due: Insert on sorted array (Juliana: 9,5)
• Due: Merge two sorted arrays as warmup for next lecture (Juliana: 5)
• Due: Simple sort by recursive and non-recursive max is stable? argue in PDF (Juliana 0)
• Content
  • Reviewed due homework
  • Pointers, references
  • Arrays and pointers
  • Matrices as multidimensional arrays. Pointers.
  • Malloc for arrays and matrices
  • Structs
  • Void *
  • Pointers to functions

Thu 31Out19

• Due: better sorted insert
• Due: max() in vertical histogram
• Due: more efficient merge
• Bitwise operators. Modulo operator.
• Excercises: one regarding Matrices, another regarding number and bit manipulation.
• Image lookup table for sorting intensities

Wed 13Out19

• Exam: programming fundamentals

Future

• Intro to advanced sorts: Merge sort, Quick Sort
  • Basic building blocks:
    • merge: merge two sorted arrays into a sorted array.
    • partition an arbitrary array into smaller and larger than a given t

Tasks + Homework

Part 1: C++ Programming practice and Review

Hello World

Celsius to/from Farenheit

Print Function graph (K&R Histogram): horizontally

• Sub exercise: max function

Implement max function recursively

Sort using max function

Print Function graph (K&R Histogram): vertically

Bucket sort

Vector and cross product exercise

• Exercise from qualify

Dados 2 vetores de inteiros A=[a1,a2,a3] e B=[b1,b2,b3] :

1. Crie uma função que leia estes vetores do teclado
2. Crie um função que calcule o produto escalar entre estes vetores.
3. Crie uma função que calcule o produto vetorial entre estes vetores.
4. Crie uma função que imprima o resultado na tela

produto escalar C = A*B=a1b1 + a2b2 + a3b3

produtor vetorial C =[a2b3 – a3b2, a3b1 – a1b3, a1b2 - a2b1]

Basic sort building blocks

• • • insert: insert on sorted array, keeping it sorted
    • merge: merge two sorted arrays into a sorted array.
    • partition an arbitrary array into smaller and larger than a given t

Tarefa 7 - Busca Binaria 30Mai19

• Implementar busca binaria de um vetor ordenado de floats
• Utilizar apenas linguagem C e sua propria implementacao
• Bonus: implementar em C++ usando a biblioteca padrao

Tarefa 8 - Ordenacao 6Jun19

• Implementar o mergesort, o quicksort e o insertion sort

Part 2: Computational Geometry problems to practice C++ programming

• • • Compute scalar and vector product of 3-vectors
    • Hash tables, Buckets for point query
    • Proximity
    • Voronoi Diagrams
    • Curve Algorithms

Homework: given a list of points, compute the closest point

• Naive algorithm
• Hash table from Programming Pearls

Homework: given a list of points, output all lines passing through each pair of points

• Line going through two points

Trabalho: Parte 1 valendo bonus, dia 2/Maio/2019, Parte2 completo 16/Maio/2019 (REMARCADA)

• Dado um labirinto na forma de uma matriz, onde os caminhos sao formados por espaco ' ',

e as paredes do labirindo sao formadas pela letra 'a' ou '8' conforme abaixo, e dada uma entrada e uma saida marcadas por espaco ' ' ou na parede de cima do labirinto, ou na parede de baixo, resolva o labirinto ou retorne 0 caso nao exista um caminho. Note que tanto as paredes ou os caminhos podem ter largura maior que 1 caractere.

• A parte 2 do trabalho valera nota e devera ser entregue 1 semana apos a parte 1. A parte 1 eh apenas bonus para incentivar o aluno a resolver o problema com ideias proprias.
• Sera dado um grande bonus.

   aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa   a
   8   8               8               8           8                   8   8
   8   8   aaaaaaaaa   8   aaaaa   aaaa8aaaa   aaaa8   aaaaa   aaaaa   8   8
   8               8       8   8           8           8   8   8       8   8
   8aaaaaaaa   a   8aaaaaaa8   8aaaaaaaa   8aaaa   a   8   8   8aaaaaaa8   8
   8       8   8               8           8   8   8   8   8           8   8
   8   a   8aaa8aaaaaaaa   a   8   aaaaaaaa8   8aaa8   8   8aaaaaaaa   8   8
   8   8               8   8   8       8           8           8       8   8
   8   8aaaaaaaaaaaa   8aaa8   8aaaa   8   aaaaa   8aaaaaaaa   8   aaaa8   8
   8           8       8   8       8   8       8           8   8           8
   8   aaaaa   8aaaa   8   8aaaa   8   8aaaaaaa8   a   a   8   8aaaaaaaaaaa8
   8       8       8   8   8       8       8       8   8   8       8       8
   8aaaaaaa8aaaa   8   8   8   aaaa8aaaa   8   aaaa8   8   8aaaa   8aaaa   8
   8           8   8           8       8   8       8   8       8           8
   8   aaaaa   8   8aaaaaaaa   8aaaa   8   8aaaa   8aaa8   aaaa8aaaaaaaa   8
   8   8       8           8           8       8   8   8               8   8
   8   8   aaaa8aaaa   a   8aaaa   aaaa8aaaa   8   8   8aaaaaaaaaaaa   8   8
   8   8           8   8   8   8   8           8               8   8       8
   8   8aaaaaaaa   8   8   8   8aaa8   8aaaaaaa8   aaaaaaaaa   8   8aaaaaaa8
   8   8       8   8   8           8           8   8       8               8
   8   8   aaaa8   8aaa8   aaaaa   8aaaaaaaa   8aaa8   a   8aaaaaaaa   a   8
   8   8                   8           8               8               8   8
   8   8aaaaaaaaaaaaaaaaaaa8aaaaaaaaaaa8aaaaaaaaaaaaaaa8aaaaaaaaaaaaaaa8aaa8

Quizz 1: C++ programming skills