Mudanças entre as edições de "Computational Geometry"

De Pontão Nós Digitais
(Thu 31Out19)
 
(23 revisões intermediárias pelo mesmo usuário não estão sendo mostradas)
Linha 1: Linha 1:
 
= ////////// Under Construction ////////// =
 
= ////////// Under Construction ////////// =
  
This is the main page of a graduate level course (Msc and PhD) in computational geometry being taught in 2019/2 at the Polytechnic Institute [http://pt.wikipedia.org/wiki/IPRJ 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.
+
[[Arquivo:Computational-geometry-concept-diagram.png|500px|center]]
  
== Lecture Log ==
+
This is the main page of a graduate level course in computational geometry being taught in 2019/2 at the Polytechnic Institute [http://pt.wikipedia.org/wiki/IPRJ 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.
  
  
=== Wed 9Out19 (twice lecture load) ===
+
 
 +
 
 +
== General Info ==
 +
* Instructor: prof. [http://rfabbri.github.io 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
 
* Hello world
 
** for loop print 10x
 
** for loop print 10x
Linha 13: Linha 24:
 
* Farenheit to/from celcius program: homework
 
* Farenheit to/from celcius program: homework
  
=== Wed 16Oct19 ===
+
==== Wed 16Oct19 ====
 
* Show results of Farenheit to Celsius
 
* Show results of Farenheit to Celsius
 
* Learn Codeblocks
 
* Learn Codeblocks
  
=== Thu 17Oct19 ===
+
==== Thu 17Oct19 ====
 
* Print function graph (K&R Histogram)
 
* Print function graph (K&R Histogram)
 
** Horizontal
 
** Horizontal
Linha 23: Linha 34:
 
*** Learn first simple sort algorithm using max
 
*** Learn first simple sort algorithm using max
  
=== Wed 23Out19 (twice lecture load) ===
+
==== Wed 23Out19 (twice lecture load) ====
 
* Due: simple sort using max
 
* Due: simple sort using max
 
* bucket sort (class exercise). Due. (student juliana: done)
 
* bucket sort (class exercise). Due. (student juliana: done)
Linha 30: Linha 41:
 
* Theory: arrays.
 
* Theory: arrays.
  
=== For Wed 30Out19 ===
+
==== 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)
 
* Overdue: Vertical Function graph (K&H Histogram)
* Due: Insert on sorted array
+
* Due: Insert on sorted array (Juliana: 9,5)
* Due: Merge two sorted arrays as warmup for next lecture
+
* 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 ===
+
==== Future ====
 
* Intro to advanced sorts: Merge sort, Quick Sort
 
* Intro to advanced sorts: Merge sort, Quick Sort
 
** Basic building blocks:  
 
** Basic building blocks:  
Linha 41: Linha 85:
 
*** partition an arbitrary array into smaller and larger than a given t
 
*** partition an arbitrary array into smaller and larger than a given t
  
 +
== Tasks + Homework ==
  
== Tarefas ==
+
=== Part 1: C++ Programming practice and Review ===
  
=== Hello World ===
+
==== Hello World ====
  
=== Celsius to/from Farenheit ===
+
==== Celsius to/from Farenheit ====
  
=== Print Function graph (K&R Histogram): horizontally ===
+
==== Print Function graph (K&R Histogram): horizontally ====
 
* Sub exercise: max function
 
* Sub exercise: max function
  
=== Implement max function recursively ===
+
==== Implement max function recursively ====
  
=== Sort using max function ===
+
==== Sort using max function ====
  
=== Print Function graph (K&R Histogram): vertically ===
+
==== Print Function graph (K&R Histogram): vertically ====
  
=== Bucket sort ===
+
==== Bucket sort ====
  
=== Basic sort building blocks ===
+
=== Vector and cross product exercise ===
 +
* Exercise from qualify
 +
 
 +
Dados 2 vetores de inteiros A=[a1,a2,a3] e B=[b1,b2,b3] :
 +
# Crie uma função que leia estes vetores do teclado
 +
# Crie um função que calcule o produto escalar entre estes vetores.
 +
# Crie uma função que calcule o produto vetorial entre estes vetores.
 +
# Crie uma função que imprima o resultado na tela
 +
:produto escalar <code>C = A*B=a1b1 + a2b2 + a3b3</code>
 +
:produtor vetorial <code>C =[a2b3 – a3b2, a3b1 – a1b3, a1b2 - a2b1]</code>
 +
 
 +
 
 +
==== Basic sort building blocks ====
 
*** insert: insert on sorted array, keeping it sorted
 
*** insert: insert on sorted array, keeping it sorted
 
*** merge: merge two sorted arrays into a sorted array.
 
*** merge: merge two sorted arrays into a sorted array.
 
*** partition an arbitrary array into smaller and larger than a given t
 
*** partition an arbitrary array into smaller and larger than a given t
  
=== Computational Geometry problems to practice C++ programming ===
+
 
 +
==== 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
 
*** Hash tables, Buckets for point query
 
*** Proximity
 
*** Proximity
Linha 70: Linha 140:
 
*** Curve Algorithms
 
*** Curve Algorithms
  
 +
===== Homework: given a list of points, compute the closest point =====
 +
* Naive algorithm
 +
* Hash table from Programming Pearls
  
=== Quizz 1: C++ programming skills ===
+
===== 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 ====
 +
***
  
== General Info ==
 
* Instructor: prof. [http://rfabbri.github.io 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
 
  
 
[[Category:Lab Macambira]] [[Category:IPRJ]]
 
[[Category:Lab Macambira]] [[Category:IPRJ]]

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

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

Computational-geometry-concept-diagram.png

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